//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 <vector<pair<int, int>>> gr;
vector <int> dist(n, INT_MAX);
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, j;

	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);
	}

	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 (se > dist[fr]) 
			continue;
		for (const auto& x : gr[fr])
		{
			dir = x.first;
			cost = x.second;
			if (dist[fr] + cost < dist[dir])
			{
				dist[dir] = dist[fr] + cost;
				pq.emplace(dir, dist[dir]);
			}
		}
	}
	
	for (i = 1; i < n; ++i)
	{
		if (dist[i] == INT_MAX)
		{
			fout << "0 ";
		}
		else
		{
			fout << dist[i] << " ";
		}
	}

	return 0;
}