#include <stdio.h>
#include <string.h>

const int NMAX=50010;
const long INF=100000000;
int c[NMAX][NMAX], n;
bool viz[NMAX];
long dist[NMAX];

void dijkstra(int nod);

int main()
{
	int x, y, cost;
	long i, j, m;
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d%ld", &n, &m);
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			c[i][j]=-1;
	for (i=0; i<m; i++)
	{
		scanf("%d%d%d", &x, &y, &cost);
		c[x][y]=cost;
	}//for i
	dijkstra(1);
	for (i=2; i<=n; i++)
		if (dist[i]==INF)
			printf("0 ");
		else
			printf("%ld ", dist[i]);
	return 0;
}//main

void dijkstra(int nod)
{
	bool gasit;
	long min;
	int i;
	for (i=1; i<=n; i++)
		dist[i]=INF;
	dist[nod]=0;
	gasit=1;
	while (gasit)
	{
		for (i=1; i<=n; i++)
		{
		  if ((c[nod][i]>=0)&&((dist[nod]+c[nod][i])<dist[i]))
		  {
			  dist[i]=dist[nod]+c[nod][i];
			  //prec[i]=nod;
		  }//if
		}//for i
		viz[nod]=1;
		gasit=0;
		min=INF;
		for (i=1; i<=n; i++)
			if ((!viz[i])&&(min>dist[i]))
			{
				min=dist[i];
				gasit=1;
				nod=i;
			}//if
	}//while
}//dijkstra