#include <bits/stdc++.h>
#include <unordered_map>
#define nmax 50006
#define MOD 1999999973
#define INF 2012345678
#define ll long long
using namespace std;
//#define fin cin
//#define fout cout

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

int n, m;
vector <pair <int, int>> L[nmax];
priority_queue <pair <int, int>> pq;
bitset <nmax> viz;
int d[nmax];

void Dijkstra(int k)
{
	int x, cost, i;
	for (i = 1; i <= n; i++)
		d[i] = INF;
	d[k] = 0;
	pq.push({ 0, k });
	while (!pq.empty())
	{
		k = pq.top().second;
		pq.pop();
		if (viz[k] == 0)
		{
			viz[k] = 1;
			for (auto w : L[k])
			{
				x = w.second;
				cost = w.first;
				if (d[x] > d[k] + cost)
				{
					d[x] = d[k] + cost;
					pq.push({ -d[x], x });
				}
			}
		}
	}
}

int main()
{
	int i, x, y, c;
	fin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y >> c;
		L[x].push_back({ c, y });
	}

	Dijkstra(1);

	for (i = 2; i <= n; i++)
		if (d[i] != INF)
			fout << d[i] << " ";
		else
			fout << "0 ";
	fout << "\n";

	fin.close();
	fout.close();
	return 0;
}