#include <bits/stdc++.h>
#include <unordered_map>
#define nmax 50006
#define MOD 9901
#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 p)
{
	int k, x, c;
	for (int i = 1; i <= n; i++)
		d[i] = INF;

	pq.push({ 0, p });
	d[p] = 0;

	while (!pq.empty())
	{
		k = pq.top().second;
		pq.pop();
		if (viz[k] != 1)
		{
			viz[k] = 1;
			for (auto w : L[k])
			{
				x = w.second;
				c = w.first;
				if (d[x] > d[k] + c)
				{
					d[x] = d[k] + c;
					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 << "-1 ";
		else
			fout << d[i] << " ";
	fout.close();
	fin.close();
	return 0;
}