#define LE 50600
#include<fstream>
#include <deque>
#include<vector>
#define inf 1<<30
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct two{int urm,cost;};
vector <pair<int,int> >A[LE];
deque <int> coada;
int i,m,n,a,b,c,nod,cost[LE];
int main()
{
	f>>n>>m;
	for(i=1;i<=m;++i)
	 {
    	f>>a>>b>>c;
	    A[a].push_back(make_pair(b,c));
	 }
	
	
	for(i=1;i<=n;++i) cost[i]=inf;
	coada.push_back(1);cost[1]=0;

	
	while (!coada.empty())
     {
		nod=coada.front();coada.pop_front();
		
		for(i=0;i<A[nod].capacity();++i)
			if(cost[nod]+A[nod][i].second < cost[A[nod][i].first])
			{
				coada.push_back(A[nod][i].first);
			    cost[A[nod][i].first]=cost[nod]+A[nod][i].second;
			}
	 } 
	
	for(i=2;i<=n;++i)
		cost[i]==inf?g<<0<<" ":g<<cost[i]<<" ";
	
	f.close();
	g.close();
}