#define INFINIT 34342
#define NMax 50002
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int,int> pereche;

int main()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	vector<pereche> G[NMax];
	int N,M,a,b,c,i,d[NMax],x,viz[NMax];
	priority_queue<pereche,vector<pereche>,greater<pereche> > pq;


	f>>N>>M;
	for(i=1;i<=M;i++)
	{
		f>>a>>b>>c;
		G[a].push_back(pereche(b,c));
		//G[b].push_back(pereche(a,c));
	}
	for(i=1;i<=N;i++)
	{
		d[i]=INFINIT;
		viz[i]=0;
	}
	d[1]=0;

	pq.push(make_pair(d[1],1));

	while(!pq.empty())
	{
		x=pq.top().second;
		pq.pop();
		if(!viz[x])
		{
		for(vector<pereche>::iterator it=G[x].begin();it!=G[x].end();it++)
		{
			if(d[it->first] > d[x] + it->second)
			{
				d[it->first]=d[x]+it->second;
				pq.push(make_pair(d[it->first],it->first));
			}

		}
		viz[x]=1;
		}

	}
	for(i=2;i<=N;i++) g<<d[i]<<" ";

	f.close();
	g.close();
	return 0;
}