#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;

vector<vector<pair<int,int>>> g;

void read()
{
	ifstream in("dijkstra.in");
	int n, m;
	in >> n >> m;
	g.resize(n, {});
	for(int i = 0; i < m; ++i)
	{
		int u, v, cost;
		in >> u >> v >> cost;
		g[u-1].emplace_back(v-1, cost);
	}
}

void compute_distance(int src)
{
	vector<int> dist(g.size(), INT_MAX);
	vector<int> prev(g.size(), -1);
	dist[src] = 0;

	auto comp = [](pair<int, int> &a, pair<int, int> &b) { 
		return a.second > b.second; 
	};
	priority_queue< 
		pair<int, int>,
		vector<pair<int, int>>,
		decltype(comp)
	> pq(comp);

	for(int i = 0; i < g.size(); ++i)
		pq.emplace(i, dist[i]);

	while(!pq.empty())
	{
		int u = pq.top().first;
		int d = pq.top().second;
		pq.pop();
		if(d == INT_MAX)
			break;
		for(auto &n : g[u])
		{
			int v = n.first;
			int d_v = n.second;
			int new_d = d + d_v;
			if(new_d < dist[v])
			{
				dist[v] = new_d;
				prev[v] = u;
				pq.emplace(v, new_d);
			}
		}
	}
	ofstream out("dijkstra.out");
	for_each(begin(dist) + 1, end(dist), [&out](int &d) { 
		if(d == INT_MAX) d = 0;
		out << d << " ";
	});
	out << endl;
}

int main()
{
	read();
	compute_distance(0);
	return 0;
}