#define _CRT_SECURE_NO_DEPRECATE

#include <set>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

FILE *f, *g;

#define DMAX 50100
#define INF 1000000000

int n, m;
struct Graf{
	int d;
	vector<int> Adj, W;
}G[DMAX];
set<pair<int, int>> v;

void Dijkstra(){
	int i, lg, root, dist, ind, next;

	for (i = 2; i <= n; i++) v.insert(make_pair(INF, i));
	v.insert(make_pair(0, 1));

	while (v.size() > 0){
		dist = (*v.begin()).first; ind = (*v.begin()).second;
		v.erase((*v.begin()));
		lg = G[ind].Adj.size();
		for (i = 0; i < lg; i++){
			next = G[ind].Adj[i];
			if (G[next].d > G[ind].d + dist){
				G[next].d = G[ind].d + dist;
				v.insert(make_pair(G[next].d, next));
			}
		}
	}
}

int main(){
	int i, x, y, w;

	f = freopen("dijkstra.in", "r", stdin);
	g = freopen("dijkstra.out", "w", stdout);

	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++){
		scanf("%d %d %d", &x, &y, &w);
		G[x].Adj.push_back(y);
		G[x].W.push_back(y);
	}

	Dijkstra();

	for (i = 2; i <= n; i++) { printf("%d ", G[i].d == INF ? 0 : G[i].d); }
	
	return 0;
}