#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e6,MAX=5e3+100,inf=0x3f3f3f3f;
long long int INF=247483647;
long long G[MAX][MAX],d[MAXN],vis[MAXN];
void Dijkstra(long long int st,long long n){
	fill(d,d+MAXN,INF);
	d[st]=0;
	long long int i,j,v;
	for(i=1;i<=n;i++){
		long long int u=-1,MIN=INF;
		for(j=1;j<=n;j++){
			if(!vis[j]&&d[j]<MIN){
				u=j;
				MIN=d[j];
			}
		}
		if(u==-1)break;
		vis[u]=1;
		for(v=1;v<=n;v++){
		    if(d[v]>d[u]+G[u][v]&&G[u][v]<INF)d[v]=d[u]+G[u][v];	
		}	
	}
	for(i=1;i<=n;i++){
		if(d[i]!=INF)cout<<d[i]<<' ';
		else cout<<-1<<' ';
	}
	cout<<endl;
}
int main()
{
	long long int n,m,u,v,w,st,i,f=0;
	cin>>n>>m;
	fill(G[0],G[0]+MAX*MAX,INF);
	for(i=1;i<=m;i++){
		cin>>u>>v>>w;
		if(w<G[u][v])G[u][v]=w;
		if(u=v)G[u][v]=0;
	}
	Dijkstra(1,n);
	
	return 0;
}