//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 <climits>
using namespace std;

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

vector <vector<pair<int, int>>> gr;
// 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;
	gr.resize(n + 1);
	for (i = 1; i <= n; ++i)
	{
		fin >> x >> y >> d;
		gr[x].emplace_back(y, d);
	}

	vector <int> dist(n+1, INT_MAX);
	vector <bool> fr(n+1, false);
	int mind, mini, cost, dir;
	dist[1] = 0;

	for (i = 1; i < n; ++i)
	{
		mind = INT_MAX;
		mini = 0			;
		for (j = 1; j <= n; ++j)
		{
			if (!fr[j] && dist[j] <= mind)
			{
				mind = dist[j];
				mini = j;
			}
		}

		fr[mini] = true;
		for (const auto& x : gr[mini])
		{
			dir = x.first;
			cost = x.second;
			if (!fr[dir] && dist[mini] != INT_MAX && dist[mini] + cost < dist[dir])
			{
				dist[dir] = dist[mini] + cost;
			}
		}
	}
	for (i = 2; i <= n; ++i)
	{
		fout << dist[i] << " ";
	}

	return 0;
}