#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

#define in "dijkstra.in"
#define out "dijkstra.out"

#define N 50005
#define INF 1 << 30

#define y second
#define c first

typedef unsigned u;
typedef pair<int, int> nod;

vector <nod> LIST[N];
vector <int> d (N, INF);
priority_queue <nod, vector<nod>, greater<nod> > H;

int n, m;

int main ()
{
	ifstream fin (in);
	fin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int x, y, c;
		fin >> x >> y >> c;
		LIST[x].push_back (nod(c, y));
	}
	fin.close();
	
	H.push (nod(0, 1));
	while (H.size()) {
		nod x = H.top(); 
		H.pop();
		if (d[x.y] != INF)
			continue;
		d[x.y] = x.c;
		for (u i = 0; i < LIST[x.y].size(); ++i)
			if (d[LIST[x.y][i].y] == INF)
				H.push (nod (x.c + LIST[x.y][i].c, LIST[x.y][i].y));
	}
	
	ofstream fout (out);
	for (int i = 2; i <= n; ++i)
		fout << ((d[i] == INF) ? 0 : d[i]) << " ";
	fout.close();
	return 0;
}