#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, -1);


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

		for (graf y : L[x.nod])
		{
			if (d[y.nod] > x.cost + y.cost || d[y.nod] == -1)
			{
				d[y.nod] = x.cost + 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] == -1 ? 0 : d[i]) << ' ';
}