#include <bits/stdc++.h>

using namespace std;

int n, m;
struct my{
	int x, y, l;
} V[250000];
int d[50050];
bool u;
int main()
{
	ifstream cin("dijkstra.in");
	ofstream cout("dijkstra.out");
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> V[i].x >> V[i].y >> V[i].l;
	}
	for (int i = 1; i <= n; i++) d[i] = -1;
	d[1] = 0;
	u = 1;
	while (u)
	{
		u = 0;
		for (int i = 1; i <= m; i++)
			if ((d[V[i].x] != -1) && ((d[V[i].y] == -1) || (d[V[i].y] > d[V[i].x] + V[i].l)))
				d[V[i].y] = d[V[i].x] + V[i].l, u = 1;
	}
	for (int i = 2; i <= n; i++)
		cout << (d[i] == -1 ? 0 : d[i]) << " ";
	return 0;
}