#include<stdio.h>
#define INF 1<<29
#define DIM 5005
int a[DIM][DIM],d[DIM],t[DIM],s[DIM],n;
void refresh ()
{
    int i,j;
    for(i=1;i<=n;++i)
        for(j=i+1;j<=n;++j)
            a[i][j]=INF;
    for(i=2;i<=n;++i)
        d[i]=INF;
}
void read ()
{
    int i,m,x1,x2,x3;
    scanf("%d%d",&n,&m);
    refresh ();
    for(i=1;i<=m;++i)
        scanf("%d%d%d",&x1,&x2,&x3),a[x1][x2]=x3;
}
void solve ()
{
    int min2,i,j,min;
    for(i=2;i<=n;++i)
    {
        d[i]=a[1][i];
        if(d[i]!=0 && d[i]!=INF)
            t[i]=1;
    }
    s[1]=1;
    for(i=1;i<=n;++i)
    {
		min=INF;
		for(j=1;j<=n;++j)
			if(d[j]<min && s[j]==0)
			{
				min=d[j];
				min2=j;
			}
		s[min2]=1;
		for(j=1;j<=n;++j)
			if(a[1][min2]+a[min2][j]<d[j] && a[1][j]!=0)
                d[j]=a[1][min2]+a[min2][j];
    }
}
void show ()
{
    int i;
    for(i=2;i<=n;++i)
        if(d[i]==INF)
            printf("0 ");
        else
            printf("%d ",d[i]);
}
int main ()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    read ();
    solve ();
    show ();
    return 0;
}