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

using namespace std;


vector<long long> dijakstra(vector<unordered_map<long long, long long>> &adj, long long n){
	vector<long long> dist(n, 2147483647);
	dist[0] = 0;
	set<pair<long long, long long>> pq;
	pq.insert({ 0, 0});
	
	while (!pq.empty()){
		long long source = (pq.begin())->second;
		pq.erase(pq.begin());
		cout << source << endl;
		for (auto node : adj[source]){
			long long 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()
{
	
	
	long long n, m;
	ifstream in("dijkstra.in");
	in >> n >> m;
	vector<unordered_map<long long, long long>> adj(n);
	for (long long i = 0; i < m; i++){
		long long source, dest, cost;
		in >> source >> dest >> cost;
		source--;
		dest--;
		adj[source][dest] = cost;
	}
	in.close();

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

	



	
}