// infoarena: problema/dijkstra //
#include <fstream>
#include <iostream>
#include <queue>
#define MAXN 50010
#define MAXM 250010
#define INF (1<<29)
using namespace std;

ifstream in("date.in");
ofstream out("date.out");

vector<int> g[MAXN];
int s[MAXM],e[MAXM],l[MAXM],i,j,n,m,d[MAXN],a,b,c,muchie;

struct cmp
{
	int operator() (int a, int b)
	{
		return l[a] > l[b];
	}
};

priority_queue<int, vector<int>, cmp> h;

int main()
{
	in>>n>>m;
	for(i=1; i<=m; i++)
	{
		in>>a>>b>>c;
		g[a].push_back(i);
		s[i] = a;
		e[i] = b;
		l[i] = c;
	}
	
	for(i=2; i<=n+1; i++)
		d[i] = INF;
	
	for(i=0; i<g[1].size(); ++i)
		h.push(g[1][i]);
	
	while(true)
	{
		muchie = m+1;
		while(!h.empty() && d[e[muchie]] != INF)
			muchie = h.top(), h.pop();
		
		if(h.empty() && d[e[muchie]] != INF)
			break;
		
		cerr<<h.top();
		
		d[e[muchie]] = d[s[muchie]] + l[muchie];
		
		for(i=0; i<g[e[muchie]].size(); ++i)
			if(d[e[g[e[muchie]][i]]] == INF)
				h.push(g[e[muchie]][i]);
	}
	
	for(i=2; i<=n; i++)
		out<<(d[i]!=INF ? d[i] : 0)<<' ';
	
	return 0;
}