//BC iara :))
/*
I: Stiti care este cea mai buna vopsea de oua?
R: Rujul de buze :))
*/
//Bellman-Ferrari
#include <stdio.h>
#define maxN 50000
#define Max maxN*1000

struct drum
{
	int d,s,cost;
}sir[maxN];

int n,m,dist[maxN];

void citire()
{
	freopen ("dijkstra.in","r",stdin);
	freopen ("dijkstra.out","w",stdout);
	scanf ("%d %d",&n,&m);
	for (int i=0;i<m;i++)
		scanf ("%d %d %d\n",&sir[i].d,&sir[i].s,&sir[i].cost);

}

void bellman_ferrari()
{
	for (int i=2;i<=n;i++)
		dist[i]=Max;
	int ok=1;
	while (ok)
	{
		ok=0;
		for (int i=0;i<=m;i++)
			if (dist[ sir[i].s ] > dist[ sir[i].d ]+sir[i].cost)
			{
				dist[sir[i].s]  =  dist[sir[i].d] + sir[i].cost;
				ok=1;
			}
	}

}

void afisare()
{
	for (int i=2;i<=n;i++)
		printf("%d ",dist[i]==Max?0:dist[i]);
}

int main ()
{
	citire();
	bellman_ferrari();
	afisare();
	return 0;
}