#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define debug(x) cerr<<#x<<": "<<(x)<<endl
using namespace std;
using llong = long long;
using vi    = vector<int>;
using vvi   = vector<vi >;
using vvvi  = vector<vvi >;
using pii   = pair<int,int>;
constexpr int    INF  = 1e9;
constexpr llong  LINF = 1e18;
constexpr double EPS  = 1e-12;
constexpr int    MOD  = 1e9+7;
template<class Type>
void line(const Type &a){int cnt=0;for(const auto &elem:a)cerr<<(cnt++?' ':'>')<<elem;cerr<<endl;}

template<class Type> inline bool chmax(Type &a,const Type &b){if(a<b){a=b;return true;}return false;}
template<class Type> inline bool chmin(Type &a,const Type &b){if(a>b){a=b;return true;}return false;}

/*ダイクストラ法*/
template<typename T>
class Dijkstra{
	using P=std::pair<T,int>;
	struct Edge{						//Edge:辺の情報を表す構造体.
		int to;
		T cost;
	};
	
	int vn;								//vn:=(ノード数).
	std::vector<std::vector<Edge> > g;	//g[v]:=(ノードvがもつ辺のリスト).
	std::vector<T> d;					//d[v]:=(ノードsからvへの最短距離).
	std::vector<int> pre;				//pre:=(逆方向経路（経路復元用）).
	T inf;
	
public:
	//constructor.
	Dijkstra():Dijkstra(0){}
	Dijkstra(size_t vn_,T inf_=1e9):vn(vn_),g(vn_),d(vn_,inf_),pre(vn_,-1),inf(inf_){}
	
	T get_inf() const{return inf;}
	void add_edge(int from,int to,T cost){//重み付き有向辺を張る.
		assert(0<=from and from<vn);
		assert(0<=to and to<vn);
		g[from].push_back((Edge){to,cost});
	}
	void dijkstra(int s){//sから各ノードへの最短距離を求める. O(|E|log|V|).
		assert(0<=s and s<vn);
		std::fill(d.begin(),d.end(),inf);
		d[s]=0;
		std::fill(pre.begin(),pre.end(),-1);
		std::priority_queue<P,std::vector<P>,std::greater<P> > pque;
		pque.emplace(0,s);
		while(!pque.empty()){
			auto [cost,v]=pque.top();
			pque.pop();
			if(d[v]<cost) continue;
			for(const Edge &e:g[v]){
				if(d[e.to]>d[v]+e.cost){
					d[e.to]=d[v]+e.cost;
					pre[e.to]=v;
					pque.emplace(d[e.to],e.to);
				}
			}
		}
	}
	T dist(int t) const{//ノードsからtへの最短距離を返す.
		assert(0<=t and t<vn);
		return d[t];
	}
	std::vector<int> get_path(int t) const{//ノードtへの最短経路を返す.
		assert(0<=t and t<vn);
		std::vector<int> path;
		for(;t!=-1;t=pre[t]) path.push_back(t);
		std::reverse(path.begin(),path.end());
		return path;
	}
};

int main(){
	int n,m;
	cin>>n>>m;

	Dijkstra<int> ob(n);
	vi self(n,INF);
	REP(i,m){
		int a,b,c;
		cin>>a>>b>>c;
		a--, b--;

		if(a==b) chmin(self[a],c);
		else ob.add_edge(a,b,c);
	}

	vvi d(n,vi(n));
	REP(i,n){
		ob.dijkstra(i);
		REP(j,n) d[i][j]=ob.dist(j);
	}

	vi ans(n,INF);
	REP(i,n) chmin(ans[i],self[i]);
	REP(i,n-1)for(int j=i+1;j<n;++j){
		chmin(ans[i],d[i][j]+d[j][i]);
		chmin(ans[j],d[i][j]+d[j][i]);
	}

	for(auto out:ans) cout<<(out==INF?-1:out)<<endl;
}
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cassert>

#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;
#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using namespace std;
typedef long long ll;
typedef pair<ll, int> P;

struct edge{
    int to, cost;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    int n, m; cin >> n >> m;
    vector<vector<edge>> g(n);
    for(int i = 0; i < m; i++){
        int a, b, c; cin >> a >> b >> c; a--; b--;
        g[a].push_back((edge){b, c});
    }
    const int INF = 1e9;
    for(int s = 0; s < n; s++){
        vector<int> d(n, INF);
        priority_queue<P, vector<P>, greater<P>> que;
        que.push(P(0, s));
        while(!que.empty()){
            P p = que.top();que.pop();
            int v = p.second;
            if(v != s && d[v] < p.first) continue;
            for(edge e : g[v]){
                if(p.first + e.cost < d[e.to]){
                    d[e.to] = p.first + e.cost;
                    que.push(P(d[e.to], e.to));
                }
            }
        }
        if(d[s] == INF) cout << -1 << endl;
        else cout << d[s] << endl;
    }
}