#include<stdio.h>

const int NMAX=50010;
const long MMAX=250010;
const long INF=100000000;

int q[NMAX], *a[NMAX], *c[NMAX], n, x[MMAX], y[MMAX], z[MMAX], d[NMAX];;
bool viz[NMAX];
long dist[NMAX], m;

void rez(int nod);

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

void rez(int nod)
{
	int p=0, u=0, i;
	for (i=0;i<=NMAX;i++)
		dist[i]=INF;
	q[u]=nod;
	if (u<NMAX)
		u++;
	else
		u=0;
	viz[nod]=1;
	dist[nod]=0;
	while (p!=u)
	{
		nod=q[p];
		if (p<NMAX)
			p++;
		else
			p=0;
		viz[nod]=0;
		for (i=1; i<=a[nod][0]; i++)
			if ((dist[nod]+c[nod][i])<dist[a[nod][i]])
			{
				if (!viz[a[nod][i]])
				{
					q[u]=a[nod][i];
					if (u<NMAX)
						u++;
					else
						u=0;
					viz[a[nod][i]]=1;
				}//if
				dist[a[nod][i]]=dist[nod]+c[nod][i];
			}//if
	}//while
}//rez