#include <stdio.h>
#define MAX_VERTICES 50001
#define MAX_EDGES 250001
#define INF 50000001

int n, m, distance[MAX_VERTICES], edges[MAX_EDGES][3];

int main()
{
	int i, j, u, v, cost;
	FILE *in = fopen("dijkstra.in", "r");
	FILE *out = fopen("dijkstra.out", "w");
	
	fscanf(in, "%d %d", &n, &m);
	for(i = 0; i < m; ++i)
		fscanf(in, "%d %d %d", &edges[i][0], &edges[i][1], &edges[i][2]);
	
	for(i = 2; i <= n; i++)
		distance[i] = INF;
	distance[1] = 0;
	
	for(i = 1; i < n; ++i)
		for(j = 0; j < m; ++j)
		{
			u = edges[j][0];
			v = edges[j][1];
			cost = edges[j][2];
			
			if(distance[u] + cost < distance[v])
				distance[v] = distance[u] + cost;
		}
	
	for(i = 2; i <= n; i++)
		fprintf(out, "%d ", distance[i]);
	fprintf(out, "\n");
	
	fclose(in);
	fclose(out);
	return 0;
}