#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=300010,INF=1e15+7;
typedef pair<int,int> p;
int n,m,s;
int h[N],e[N*5],ne[N*5],w[N*5],idx;
long long dist[N];
bool vis[N];
inline void add(int a,int b,int c){
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dij(int s){
	memset(dist,0x3f,sizeof dist);
	priority_queue<p,vector<p>,greater<p>> q;
	dist[s]=0;
	q.push(p(dist[s],s));
	while(!q.empty()){
		int t=q.top().second;
		q.pop();
		if(vis[t]) continue;
		vis[t]=1;
		
		for(int i=h[t];~i;i=ne[i]){
			int j=e[i];
			if(dist[j]>dist[t]+w[i]){
				dist[j]=dist[t]+w[i];
				if(!vis[j]){
					q.push(p(dist[j],j));
				}
				
			}
		}
	}
}
signed main(){
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof h);
	for(int i=1;i<=n+10;i++){
		dist[i]=INF;
	}
	for(int i=1;i<=m;i++){
		int a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		add(a,b,c);
	}
	dij(1);
	for(int i=1;i<=n;i++){
		if(dist[i]==INF) printf("-1 ");
		else printf("%lld ",dist[i]);
	}
	return 0;
}