#include <iostream>
#include <fstream>
#include <queue>
#define f first
#define s second
#define inf 1000000500
#define NMAX 50000

using namespace std;

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

int n, m, cost[NMAX+10], viz[NMAX+10];
vector <pair <int, int> > nod[NMAX+10];
priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > pq;

int main()
{
	fin >> n >> m;
	for(int i=1; i<=m; i++)
		{	int nod1, nod2, cost;
			fin >> nod1 >> nod2 >> cost;
			nod[nod1].push_back({cost, nod2});
		}	
	for(int i=2; i<=n; i++)
		cost[i] = inf;
	pq.push({0, 1});
	while(!pq.empty())
		{	pair <int, int> x = pq.top();
			pq.pop();
			if(viz[x.s]) continue;
			viz[x.s] = 1;
			for(auto u : nod[x.s])
				{	int d = x.f + u.f;
					if(d < cost[u.s])
						{	cost[u.s] = d;
							pq.push({d, u.s});
						}
				}
		}
	for(int i=2; i<=n; i++)
		{	if(cost[i] == inf)
				fout << 0 << ' ';
			else
				fout << cost[i] << ' ';
		}
	fout << '\n';
	return 0;
}