#include <fstream>
#include <vector>
#include <set>
#include <queue>

#define inf 50000001
#define nmax 50001
using namespace std;

queue<int> Q;
vector<vector<pair<int, int> > > v;
int D[nmax];
int T[nmax];
int main() {
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");

	
	int n, m;
	f >> n >> m;
	
	v.resize(n+3);

	while (m--) {
		int a, b, c;
		f >> a >> b >> c;
		v[a].push_back(make_pair(b, c));

	}
	for (int i = 1; i <= n; ++i) D[i] = inf;
	D[1] = 0;T[1] = 1;
	Q.push(1);
	while (!Q.empty()) {
		int nod = Q.front(); Q.pop();

		T[nod] = 0;
		for (int i = 0; i < v[nod].size(); ++i) if (D[nod] + v[nod][i].second < D[v[nod][i].first]) 
		{
			 D[v[nod][i].first] = D[nod] + v[nod][i].second;
			 
			 if (!T[v[nod][i].first]) Q.push(v[nod][i].first), T[v[nod][i].first]=1;

		}
	}
	for (int i = 2; i <= n; ++i) {
		if (D[i] == inf) D[i] = 0;
		if (i!=2) g << " ";
		g << D[i];
	}
	g << '\n';
	return 0;
}