#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 50005;
int n, m;
vector<pair<int, int>>G[NMAX];
int d[NMAX];

void read()
{
	f >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, c;
		f >> x >> y >> c;
		G[x].push_back({ y, c });
	}
}

void dij(int start)
{
	priority_queue<pair<int, int>>pq;
	pq.push({ 0, start });
	while (!pq.empty())
	{
		auto varf = pq.top();
		pq.pop();
		if(d[varf.second] != 0)
			continue;
		d[varf.second] = -varf.first;
		for (auto vecin : G[varf.second])
		{
			if (d[vecin.first] == 0)
			{
				pq.push({ -(-varf.first + vecin.second), vecin.first });
			}
		}
	}
}

int main()
{
	read();
	dij(1);
	for (int i = 2; i <= n; i++)
	{
		if (d[i] == 0)
			g << "0 ";
		else
			g << d[i] << " ";
	}
}