using namespace std;
#include<fstream>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define pq priority_queue
#define mp make_pair
#define Nmax 50010
#define INF 2000000000
#define InFile "dijkstra.in"
#define OutFile "dijkstra.out"
#define pair pair<int,int>
struct QueueCompare
{
bool operator () (const pair &a, const pair &b) const
	{
	return a.second>b.second;
	}
};
int main ()
{
	int i,n,m,x,y,cost,d[Nmax];
	pq<pair, vector<pair > , QueueCompare> heap;
	vector<pair> c[Nmax];
	ifstream f(InFile);
	f>>n>>m;
	/*for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			c[i][j]=INF;
		d[i]=INF;
	}
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>cost;
		c[x][y]=cost;
	}*/
	for(i=2;i<=n;i++)
		d[i]=INF;
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>cost;
		c[x].push_back(mp(y,cost));
	}
	f.close();
	d[1]=0;
	heap.push(mp(1, 0));
	while(!heap.empty())
	{
		cost=heap.top().second , x=heap.top().first;
		heap.pop();
		for(vector<pair>::iterator it=c[x].begin();it!=c[x].end();it++)
			if(d[(*it).first]>cost+(*it).second)
			{
				d[(*it).first]=cost+(*it).second;
				heap.push(mp((*it).first,d[(*it).first]));
			}
	}
	ofstream g(OutFile);
	for(i=2;i<=n;i++)
		g<<(d[i]==INF ? 0:d[i] ) <<" ";
	return 0;
}