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


using namespace std;


vector<int> dijakstra(vector<unordered_map<int, int>> &adj, int n){
	vector<int> dist(n, 999999999);
	dist[0] = 0;
	set<pair<int, int>> pq;
	pq.insert({ 0, 0});
	
	while (!pq.empty()){
		int source = (pq.begin())->second;
		pq.erase(pq.begin());
		
		for (auto node : adj[source]){
			int to = node.first, cost = node.second;
			if (dist[to] > dist[source] + cost){
				//pq.erase({ dist[to], to });
				pq.insert({ dist[source] + cost, to});
				dist[to] = dist[source] + cost;
			}
		}

	}
	
	return dist;


}

int main()
{
	
	
	int n, m;
	ifstream in("dijkstra.in");
	in >> n >> m;
	vector<unordered_map<int, int>> adj(n);
	for (int i = 0; i < m; i++){
		int source, dest, cost;
		in >> source >> dest >> cost;
		source--;
		dest--;
		adj[source][dest] = cost;
	}
	in.close();

	vector<int> dist = dijakstra(adj,n);
	ofstream out("dijkstra.out");
	for (int i = 1; i < n; i++)
		out << dist[i]<<' ';
	out << endl;
	out.close();
	return 0;

	



	
}