#include<stdio.h>
int v[10000][3],c[10000],i,x,y,j,ok;
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&x, &y);
    for(i=2;i<=x;i++)c[i]=2000000000;
	for(i=1;i<=y;i++)
	{	
		scanf("%d %d %d",&v[i][0],&v[i][1],&v[i][2]);
		if(v[i][0]==1)c[v[i][1]]=v[i][2];
	}
    while(!ok)
    {
        ok=1;
		for(j=1;j<=y;j++)
        {    
			if(c[v[j][1]]>c[v[j][0]]+v[j][2])
				{
					c[v[j][1]]=c[v[j][0]]+v[j][2];
					ok=0;
				}
    	}
	}
    for(i=2;i<=x;i++)printf("%d ",c[i]);
    return 0;
}