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

queue<int> C;
int n,m,D[100000],x,y,z;
struct nod
{
	int nr,lun;
	nod *next=0;
	
} *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;
	  }
	C.push(1);
	while(!C.empty())
	{ 
		r=A[C.front()];
		for(nod *i=r;i;i=i->next)
		{
		     if(!V[i->nr]) C.push(i->nr),V[i->nr]=1,D[i->nr]=i->lun+D[C.front()];
		     else {
		     	D[i->nr]=min(D[i->nr],D[C.front()]+i->lun);
			 }
		 }
		 C.pop();
		     
	}
	for(int i=2;i<=n;i++) cout<<D[i]<<" ";

}