#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
#define nmax 50005
#define inf (1<<30)
#define dist first
#define node second
using namespace std;

set <pair <int, int> > s;
vector <int> v[nmax], w[nmax];
int n, m, a, b, c, best[nmax];

void dijkstra() {
	int x, newDist;
	while(!s.empty()) {
		x = s.begin()->node;
		s.erase(s.begin());

		if(best[x] == inf) return;

		for(int i=0; i<v[x].size(); i++) {
			newDist = best[x] + w[x][i];
			if(newDist < best[v[x][i]]) {
				s.erase(make_pair(best[v[x][i]], v[x][i]));
				s.insert(make_pair(newDist, v[x][i]));
				best[v[x][i]] = newDist;
			}
		}
	}
}

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

	f>>n>>m;
	for(int i=2; i<=n; i++) best[i] = inf;
	for(int i=1; i<=m; i++) {
		f>>a>>b>>c;
		v[a].push_back(b);
		w[a].push_back(c);
	}
	for(int i=1; i<=n; i++) s.insert(make_pair(best[i], i));

	dijkstra();

	for(int i=2; i<=n; i++) g<<best[i]<<" "; g<<"\n";

	return 0;
}