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

using namespace std;
struct asdf{
public:
	int a;
	int b;
	friend bool operator<(const asdf& asdf1, const asdf& asdf2);
};

bool operator<(const asdf& asdf1, const asdf& asdf2){
	if (asdf1.a<asdf2.a)
		return true;
	else if (asdf1.a == asdf2.a && asdf1.b < asdf1.b)
		return true;
	return false;

}

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

	}
	
	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;
		adj[--source][--dest] = cost;
	}
	in.close();

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

	



	
}