#include<bits/stdc++.h>
#define N 250000
#define inf 0x3f3f3f3f
using namespace std;
struct qwe{
	int u,v,w;
}edge[250000];
long long n,m,s,t;
long long u[N],v[N],w[N],dis[N];
void bellman_ford(){
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	for(int k=1;k<n;k++){
		bool check=0;
		for(int i=1;i<=m;i++){
			int u=edge[i].u;
			int v=edge[i].v;
			int w=edge[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				check=1;
			}
			if(dis[u]>dis[v]+w){
				dis[u]=dis[v]+w;
				check=1;
			}
		}
		if(!check)	return ;
	}
}
int main(){
	scanf("%lld%lld",&n,&m);
	s=1;
	for(int i=1;i<=m;i++){
		long long a,b,l;
		scanf("%lld%lld%lld",&a,&b,&l);
		edge[i].u=a;
		edge[i].v=b;
		edge[i].w=l;
	}
	bellman_ford();
	for(int i=2;i<=n;++i){
        if(dis[i]==inf)
	        printf("-1");
	    printf("%lld ",dis[i]);
	    
	}
	return 0;
}