#include <stdio.h>
#include<iostream>
#define NMAX 50001
#define MMAX 250001
#define INFI 0x3f3f3f3f
int *a[NMAX],*c[NMAX],ce[MMAX],v[NMAX],v1[NMAX],d[NMAX],t[NMAX];
int j,i,m,n;
int main(void)
{
freopen("dijkstra.in","r",stdin);
int xx,yy,di;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
	{
	scanf("%d%d%d",&xx,&yy,&di);
	v[xx]++;
	
    a[xx]=(int*)realloc(a[xx],(v[xx]+1)*sizeof(int));
    a[xx][v1[xx]+1]=yy;
    
    c[xx]=(int*)realloc(c[xx],(v[xx]+1)*sizeof(int));
	c[xx][v1[xx]+1]=di;
	v1[xx]++;
	}
fclose(stdin);

freopen("dijkstra.out","w",stdout);
                  /*
for(i=1;i<=n;i++)
    {
    for(j=1;j<=v[i];j++)
	   printf("%d ",a[i][j]);
    printf("\n");
    }               */
memset(d, INFI, sizeof(d));  
int s=1;
d[s]=0;
t[s]=0;
ce[1]=s;
int p,u,nod;
p=u=1;
while(p<=u)
	{
	nod=ce[p];
	for(i=1;i<=v[nod];i++)
		{
        if(d[a[nod][i]]>d[nod]+c[nod][i])
            {
            u++;
            ce[u]=a[nod][i];
            
            d[a[nod][i]]=d[nod]+c[nod][i];
            t[a[nod][i]]=nod;
            }
		}
	p++;
	}
for(i=2;i<=n;i++)
    {
    if(d[i]==INFI) printf("0 ");
    else printf("%d ",d[i]);
    }
printf("\n");
fclose(stdout);
return 0;
}