#include <fstream>
#include <vector>
#include <queue>
using namespace std;
string file = "dijkstra";
ifstream cin(file + ".in");
ofstream cout(file + ".out");
struct graf {
	int nod;
	int cost;

	bool operator < (const graf& y) const
	{
		return cost > y.cost;
	}
};
vector <graf> L[50001];


vector <int> d(50001, 1000000000);


void bfs()
{
	priority_queue <graf> Q;
	d[1] = -1;
	Q.push({ 1,0 });
	while (!Q.empty())
	{
		int x = Q.top().nod;
		Q.pop();

		for (graf y : L[x])
		{
			if (d[y.nod] > d[x] + y.cost || d[y.nod] == 0)
			{
				d[y.nod] = d[x] + y.cost;
				Q.push ({ y.nod,d[y.nod] });
			}
		}
	}
}
int main() {
	int n, m, x, y, z;
	cin >> n >> m;
	while (m--)
	{
		cin >> x >> y >> z;
		L[x].push_back({ y,z });
	}
	bfs();
	for (int i = 2; i <= n; i++)
		cout << d[i] << ' ';
}