#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define ll long long
using namespace std;
using P = pair<int, int>;

struct E {
    int to, co;
    E(int to=0, int co=0):
    to(to), co(co) {}
};

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<E>> g(n);
    rep(i, m){
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        g[a].emplace_back(b, c);
    }
    const int INF = 1001001001;
    rep(sv, n){
        vector<int> dist(n, INF);
        priority_queue<P, vector<P>, greater<P>> q;
        auto push = [&](int v, int d){
            if(dist[v] <= d) return;
            dist[v] = d;
            q.emplace(d, v);
        };
        for (auto&&  e: g[sv]) push(e.to, e.co);
        while(!q.empty()){
            int d = q.top().first;
            int v = q.top().second;
            q.pop();
            if(dist[v] != d) continue;
            for (auto&& e : g[v]){
                push(e.to, d+e.co);
            }
        }
        int ans = dist[sv];
        if (ans == INF) ans = -1;
        cout << ans << endl;
    }
}
	// author : sharad12arse
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define INF LONG_LONG_MAX
#define gcd __gcd

const long mxN=2001;
const ll ax=1e12;

ll n,m;

vector<pair<ll,ll> > adj[mxN];
vector<ll> vst(mxN),dst(mxN);

ll bfs(ll x){
	priority_queue<pair<ll,ll>,vector<pair<ll,ll> > ,greater<pair<ll,ll> > > pq;
	pq.push({0,x});
	int u,v;
	while(pq.size()){
//		cout<<pq.size()<<"\n";
		u=pq.top().second;
		v=pq.top().first;
		pq.pop();
		for(int i=0;i<adj[u].size();i++){
//			cout<<v+adj[u][i].second<<" "<<dst[adj[u][i].first]<<"\n";
			if((v+adj[u][i].second)<dst[adj[u][i].first]){
				dst[adj[u][i].first]=v+adj[u][i].second;
				pq.push({v+adj[u][i].second,adj[u][i].first});
			}
		}
	}
	return dst[x];
}

void solve(){
	cin>>n>>m;
	ll u,v,w;
	for(int i=0;i<m;i++){
		cin>>u>>v>>w;
		adj[u].push_back({v,w});
	}
	vector<ll> ans(n+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dst[j]=ax;
		}
		ll y=bfs(i);
		if(y>=ax){
			ans[i]=-1;
		}else{
			ans[i]=y;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<"\n";
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll t=1;
//	cin>>t;
	while(t--)
		solve();
}