#include <bits/stdc++.h>

using namespace std;

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

struct arc
{
	int x, c;
};

vector < arc > v[100002];
queue < int > q;

int n, m, p;
int dist[100002];
bool viz[100002];

void dijkstra2(int start)
{
	for (int i = 1; i <= n; i++)
		dist[i] = 999999999;
	dist[start] = 1;
	viz[start] = 1;
	q.push(start);
	while (!q.empty())
	{
		int i = q.front();
		q.pop();
		int m = v[i].size();
		for (int k = 0; k < m; k++)
		{
			int j = v[i].at(k).x;
			int c = v[i].at(k).c;
			if (dist[j] > dist[i] + c)
			{
				dist[j] = dist[i] + c;
				viz[j] = 1;
				q.push(j);
			}
		}
	}
}

int main()
{
	in >> n  >>m;
	for (int k = 1; k <= m; k++)
	{
		int i, j, c;
		in >> i >> j >> c;
		v[i].push_back({ j,c });
		v[j].push_back({ i,c });
	}
	dijkstra2(1);
	for (int i = 1; i <= n; i++)
		if (viz[i])
			out << dist[i] << ' ';
		else out << -1 << ' ';
	return 0;
}