#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define INF 9999999

set <pair<int,int>> C;
int n,m,D[100000],x,y,z;
struct nod
{
	int nr,lun;
	nod *next,*pr;
	
} *p,*r,*A[100000];
bool V[1000000];
	
int main()
{
	ifstream cin("dijkstra.in");
	ofstream cout("dijkstra.out");
	cin>>n>>m;
	for(int i=0;i<m;i++)
	  {
	  	r= new nod;
	  	cin>>x>>y>>z;
	  	r->nr=y;
	  	r->lun=z;
	  	r->next=A[x];
	  	if(A[x])A[x]->pr=r;
	    A[x]=r;
	  }
	  for(int i=1;i<=n;i++)
	  {
	  	D[i]=INF;
	  }
	  D[1]=0;
	C.insert({0,1}); V[1]=1;
	while(!C.empty())
	{ 
		r=A[C.begin()->second];
		for(nod *i=r;i;i=i->next)
		{
		     if(!V[i->nr]){
			 	D[i->nr]=min(D[i->nr],D[C.begin()->second]+i->lun);
			 	C.insert({D[i->nr],i->nr});
			 }
		 }
		 V[C.begin()->second]=1;
		 C.erase(C.begin());
		     
	}
	for(int i=2;i<=n;i++) cout<<D[i]<<" ";

}