// infoarena: problema/dijkstra //

#include <fstream>
#include <vector>
#include <queue>
#define MAXN 50010
#define INF (1<<30)
using namespace std;

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

int n,m,i,j,d[MAXN],_;

struct MUCHIE
{
	int b,e,l;
};

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

vector<MUCHIE> g[MAXN];
vector<MUCHIE>::iterator it,e;
priority_queue<MUCHIE, vector<MUCHIE>, cmp> q;
MUCHIE tmp,M;

int main()
{
	in>>n>>m;
	for(i=1; i<=m; i++)
	{
		in>>tmp.b>>tmp.e>>tmp.l;
		g[tmp.b].push_back(tmp);
	}
	
	/*for(i=1; i<=n; i++)
	{
		cerr<<i<<": ";
		for(it = g[i].begin(); it!=g[i].end(); it++)
			cerr<<"{ "<< it->b <<", "<< it->e <<", " << it->l <<"} ";
		cerr<<'\n';
	}*/	
	
	for(it=g[1].begin(); it!=g[1].end(); it++)
		q.push(*it);
	
	for(i=2; i<=n; i++)
		d[i] = INF;
	
	for(_=1; _<n; _++)
	{
		M.e = 0;
		while(!q.empty() && d[M.e] != INF)
			M = q.top(), q.pop();
		
		if(d[M.e] != INF)
			break;
		
		d[M.e] = d[M.b] + M.l;
		for(it=g[M.e].begin(),e=g[M.e].end(); it!=e; it++)
			if(d[it->e] == INF)
				q.push(*it);
	}
	
	for(i=2; i<=n; i++)
		out<< (d[i]==INF ? 0 : d[i])<<' ';
	
	return 0;
}