#include<string>
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<list>
#include<map>
#include<set>
#include<unordered_map>


using namespace std;


vector<int> dijkstra(vector<vector<int>> &g,vector<vector<int>> &c, int n){
	vector<int> d(n + 2, 1000000000);
	set<pair<int, int>>pq;
	d[1] = 0;
	pq.insert({ 0, 1 });
	while (!pq.empty()){
		int cost = (pq.begin())->first,
			source = (pq.begin())->second;
		pq.erase(*pq.begin());
		for (int i = 0; i < g[source].size();i++)
			if (d[g[source][i]] > cost + c[source][i]){
				d[g[source][i]] = cost + c[source][i];
				pq.insert({ d[g[source][i]], g[source][i] });
			}
	}
	return d;

}

int main()
{
	int n, m;
	ifstream in("dijkstra.in");
	in >> n >> m;
	vector<vector<int>> g(n + 2), c(n + 2);
	for (int i = 0; i < m; i++)
	{
		int a, b, d;
		in >> a >> b >> d;
		g[a].push_back(b);
		c[a].push_back(d);
	}
	in.close();

	vector<int> d = dijkstra(g, c, n);
	ofstream out("dijkstra.out");
	for (int i = 2; i <= n; i++)
		out << d[i]<<' ';
	out << endl;
	out.close();

	



	
}