#include<iostream>
#include<fstream>
#include<vector>
#include<set>
using namespace std;
vector<int>M[50001],C[50001];
int d[50001],n,m;
set< pair<int,int> >P;
#define INF 10000000
void dijkstra()
{
	int i,cost,nod;
	for(i=2; i<=n; i++) d[i]=INF;
	P.insert(make_pair(0,1));
	while(P.size()>0)
	{
		cost=(*P.begin()).first; 
		nod=(*P.begin()).second;
		P.erase(*P.begin());
		for(i=0; i<M[nod].size(); i++)
			if(d[M[nod][i]]>cost+C[nod][i])
				{
					d[M[nod][i]]=cost+C[nod][i];
					P.insert(make_pair(d[M[nod][i]],M[nod][i]));
			}
	}
}
int main()
{
	int x,y,c,i;
	ifstream f("dijkstra.in");
	f>>n>>m;
	for(i=1; i<=m; i++)
		{
			f>>x>>y>>c;
			M[x].push_back(y);
			C[x].push_back(c);
	}
	f.close();
	dijkstra();
	ofstream g("dijkstra.out");
	for(i=2; i<=n; i++)
		if(d[i]!=INF)
		g<<d[i]<<" ";
	g.close();
		
}