#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
int n,m,a,b,c,dis[200005];
vector<pii>g[200005];
void bfs(int x){
	priority_queue<pii>q;
	for(int i=1;i<=n;i++)dis[i]=1e18;
	for(pii i:g[x]){
		if(dis[i.first]>i.second){
			dis[i.first]=i.second;
			q.push({dis[i.first],i.first});	
		}
	}
	while(!q.empty()){
		int pos=q.top().second;
		q.pop();
		for(pii i:g[pos]){
			if(dis[i.first]>dis[pos]+i.second){
				dis[i.first]=dis[pos]+i.second;
				q.push({dis[i.first],i.first});
			}
		}
	}
	if(dis[x]!=1e18)printf("%lld\n",dis[x]);
	else printf("-1\n");
}
signed main () {
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&a,&b,&c);
		g[a].push_back({b,c});
	}
	for(int i=1;i<=n;i++)bfs(i);
	return 0;
}