#include<stdio.h>
#define NMAX 10000
#define INFINIT 10000
int n,m,C[NMAX][NMAX];


void Citire(void)
{
	int i,j,c;
	freopen("dijkstra.in","r",stdin);
	scanf("%d %d\n",&n,&m);
	for(i=1; i<=n; i++)
		for(j=1; j<=n; j++)
			if(i!=j)
				C[i][j]=INFINIT;
	for(; m>0; m--)
	{
		scanf("%d %d %d\n",&i,&j,&c);
		C[i][j]=c;
	}
}

void Afisare(int d[NMAX])
{
	int i;
	freopen("dijkstra.out","w",stdout);
	for(i=2; i<=n; i++)
		if(d[i]==INFINIT)
			printf("%d ",0);
		else
			printf("%d ",d[i]);
}

void Dijkstra(int x0)
{
    int i, min, k, ok;
    int viz[NMAX], d[1001], tata[NMAX];
	
    for (i=1; i<=n; i++)
	{
		d[i] = C[x0][i];
        tata[i] = x0;
        viz[i] = 0;
    }
    tata[x0] = 0; viz[x0] = 1; ok = 1;
	
	
    while (ok) 
	{
        min = INFINIT;
        for (i = 1; i<=n; i++)
            if (!viz[i] && min>d[i]) 
			{
                min = d[i];
                k = i;
            }
        if (min != INFINIT) 
		{
            viz[k] = 1;
            for (i = 1; i<=n; i++)
               if (!viz[i] && d[i]>d[k]+C[k][i]) 
			   {
                   d[i] = d[k]+C[k][i];
                   tata[i] = k;
               }
        }
        else ok = 0;
    }
	
	Afisare(d);
	
}

int main()
{
	Citire();
	Dijkstra(1);


	return 0;
}