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

const int NMAX=50010;
const long MMAX=250010;
const long INF=100000000;
int n, x[MMAX], y[MMAX], z[MMAX], d[NMAX];
long dist[NMAX], m;

void rez(int nod);

int main()
{
	long 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
	rez(1);  //bellman-ford
	for (i=2; i<=n; i++)
		if (dist[i]==INF)
			printf("0 ");
		else
			printf("%ld ", dist[i]);
	return 0;
}//main

void rez(int nod)
{
	long i, j;
	for (i=1; i<=n; i++)
		dist[i]=INF;
	dist[nod]=0;
	for (j=1; j<=n; j++)
		for (i=0; i<m; i++)
			if (dist[y[i]]>(dist[x[i]]+z[i]))
				dist[y[i]]=dist[x[i]]+z[i];
}//rez