#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define N 50005
#define MARE 0x3f3f3f3f
int main () {
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	vector< pair<int,int> > v[N];
	int d[N],n,m,a,b,c,x,i;
	bool f[N];
	queue <int> q;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;++i){
		scanf("%d%d%d",&a,&b,&c);
		v[a].push_back(make_pair(b,c));
	}
	memset(d,MARE,sizeof(d));
	memset(f,false,sizeof(f));
	d[1]=0;
	f[1]=true;
	q.push(1);
	while(!q.empty()){
		x=q.front();
		q.pop();
		f[x]=false;
		for(vector < pair<int,int> >::iterator it=v[x].begin();it!=v[x].end();++it)
			if(d[x]+it->second<d[it->first]){
				d[it->first]=d[x]+it->second;
				if(!f[it->first]){
					q.push(it->first);
					f[it->first]=true;
				}
			}
	}
	for(i=2;i<=n;++i)
		if(d[i]==MARE)
			printf("0 ");
		else
			printf("%d ",d[i]);
	return 0;
}