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

#define inf 0x3f3f3f3f
#define nmax 50001
using namespace std;


vector<pair<int, int> >  v[nmax];


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

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

	}
	int D[nmax];
	bool T[nmax];
	memset(D, inf, sizeof(D));
	memset(T, 0, sizeof(T));
	D[1] = 0;T[1] = true;
	queue<int> Q;
	Q.push(1);
	
	while (!Q.empty()) {
		int nod = Q.front(); Q.pop();

		T[nod] = false;
		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]=true;

		}
	}
	ofstream g("dijkstra.out");
	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;
}