#include<cstdio>
const int I=2000000;
int a[250001][4],d[50001],n,k,o=1,i,j,c,m,r=1;
int main()
{
    freopen("dijkstra.in","r",stdin),freopen("dijkstra.out","w",stdout),scanf("%d%d",&n,&m);
	for(i=2;i<=n;i++)
        d[i]=I;
	for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i][1],&a[i][2],&a[i][3]);
        if(a[i][1]==1)
            d[a[i][2]]=a[i][3];
    }
	while(o&&r<n)
	{
	    o=0;
		for(i=1;i<=m;i++)
            if(d[a[i][2]]>d[a[i][1]]+a[i][3])
                d[a[i][2]]=d[a[i][1]]+a[i][3],o=1;
		r++;
	}
    for(i=2;i<=n;i++)
        printf("%d ",d[i]==I?0:d[i]);
}