# include <stdio.h>

# define input "bellman.in"
# define output "bellman.out"

# define max 1001
# define INF 128000

struct muchie
{
       int x,y,c;
}e[250000];

int i,j,n,d[50000],x,y,c,k,m;
int ok,nr;

int main()
{
	freopen(input, "r", stdin);
	freopen(output, "w", stdout);

    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
       d[i] = INF;
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].c);

    d[1] = 0;
    
    for(ok = nr = 1;ok && nr < n;nr++)
    {
           ok = 0;
           for(k=1;k<=m;k++)
           {
               x = e[k].x;
               y = e[k].y;
               c = e[k].c;
               if(d[y] > d[x]+c)
               {
                   d[y] = d[x]+c;
                   nr = 1;
               }
           }
    }
    for(i=2;i<=n;i++)
        printf("%d ",d[i]);


	return 0;
}