//https://infoarena.ro/problema/dijkstra
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("fast-math")
//#pragma GCC optimize ("unroll-loops")
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector <int> dist;
vector <bool> b;
vector <vector<pair<int, int>>> gr;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// first pana unde, second distanta
int main()
{
	/*ios_base::sync_with_stdio(false);
	cin.tie(NULL);*/
	int n, m, x, y, d, i;

	fin >> n >> m;
	//cout << n << m << "\n";
	gr.resize(n);
	for (i = 0; i < m; ++i)
	{
		fin >> x >> y >> d;
		//cout << x << " " << y << "\n";
		gr[x-1].emplace_back(y-1, d);
	}

	b.assign(n, false);
	dist.assign(n, INT_MAX);
	int fr, se, dir, cost;
	
	dist[0] = 0;
	pq.emplace(0, 0);

	while (!pq.empty())
	{
		fr = pq.top().first;
		se = pq.top().second;
		pq.pop();
		if (b[se] == true)
			continue;
		b[se] = true;
		for (const auto& x : gr[se])
		{
			dir = x.first;
			cost = x.second;
			if (dist[se] + cost < dist[dir])
			{
				dist[dir] = dist[se] + cost;
				pq.emplace(dist[dir], dir);
			}
		}
	}
	
	for (i = 1; i < n; ++i)
	{
		if (dist[i] == INT_MAX)
		{
			fout << "0 ";
		}
		else
		{
			fout << dist[i] << " ";
		}
	}

	return 0;
}