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

set <pair<int,int>> C;
int n,m,D[100000],x,y,z;
struct nod
{
	int nr,lun;
	nod *next;
	
} *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];
	    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];
		int n=C.begin()->second;
		C.erase(C.begin());
		for(nod *i=r;i;i=i->next)
		{
		     if(!V[i->nr]){	
		        if(D[i->nr]!=INF)C.erase(C.find({D[i->nr],i->nr}));
				 D[i->nr]=min(D[i->nr],D[n]+i->lun);
				 C.insert({D[i->nr],i->nr});
			 
			 }
		 }
		 V[n]=1;
		 
		     
	}
	for(int i=2;i<=n;i++) cout<<(D[i]==INF ? 0:D[i])<<" ";

}