#include<cstdio>
#include<queue>
using namespace std;
queue<int> q;
vector<unsigned short> v[50005];
short c[50005][50005];
bool inc[50005];
int r[50005];
int main()
{
	freopen ("dijkstra.in","r",stdin);
	freopen ("dijkstra.out","w",stdout);
	int n,m;
	scanf ("%d%d",&n,&m);
	for(int i=0;i<50005;i++){
		r[i]=2000000000;
		for(int j=0;j<50005;j++)
			c[i][j]=30000;
	}
	while(m--){
		int x,y,z;
		scanf ("%d%d%d",&x,&y,&z);
		v[x].push_back (y);
		c[x][y]=z;
	}
	q.push (1);
	inc[1]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		inc[x]=0;
		for(vector<unsigned short>::iterator it=v[x].begin();it!=v[x].end();it++)
			if(r[x]+c[x][*it]<r[*it]){
				r[*it]=r[x]+c[x][*it];
				if(!inc[*it]){
					inc[*it]=1;
					q.push (*it);
				}
			}
	}
	for(int i=2;i<=n;i++)
		printf ("%d ",r[i]);
	return 0;
}