#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#define maxn 50000
#define maxm 300000
#define INF 20001
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int N, M;
int **graf;
int SePoate[maxn];
int viz[maxn];
int dist[maxn];

void BFS(int nod) {
	queue <int> coada;
	coada.push(nod);
	SePoate[nod] = 1;
	while (!coada.empty()) {
		int sel = coada.front();
		coada.pop();
		for (int i = 1; i <= N; ++i) {
			if (graf[sel][i] && SePoate[i] == 0) {
				coada.push(i);
				SePoate[i] = 1;
			}
		}
	}
	
}

void dij() {
	for (int i = 1; i <= N; ++i)
		dist[i] = INF;
	dist[1] = 0;
	int select = 1;
	//BFS(1);
	for (int i = 1; i <= N; ++i) {
		int dimMin = INF;
		int indMin = 0;
		viz[select] = 1;
		for (int j = 1; j <= N; ++j) {
			if (graf[select][j] != -1 && (graf[select][j] + dist[select] < dist[j]) && viz[j] == 0) {
				dist[j] = graf[select][j] + dist[select];
			}
		}
		for (int j = 1; j <= N; ++j) {
			if (dist[j] < dimMin && viz[j] == 0) {
				dimMin = dist[j];
				indMin = j;
			}
		}
		select = indMin;
	}
	for (int i = 2; i <= N; ++i)
		g << dist[i] << " ";
}

int main()
{
	f >> N >> M;
	graf = new int*[N + 1];
	for (int i = 1; i <= N; ++i) {
		graf[i] = new int[N + 1];
	}
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j)
			graf[i][j] = -1;
	}
	for (int i = 1; i <= M; ++i) {
		int x, y, c;
		f >> x >> y >> c;
		graf[x][y] = c;
	}
	dij();

	system("pause");
	return 0;
}