#include<fstream>
#include<vector>
#define infin 250000003
using namespace std;



ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int v[50002];
struct muchie
{
	int inf;
	int cost;
};
	
vector <muchie> lv[50002];
int pret[50002];
int arb[132000];
int n,mm;


void actualizare(int nod,int st,int dr,int x,int cost)
{if(st==dr)arb[nod]=cost;
   else 
   {
	int m;
	m=(st+dr)/2;
	if(x<=m)actualizare(2*nod,st,m,x,cost);
	   else actualizare(2*nod+1,m+1,dr,x,cost);
     if(arb[2*nod]<arb[2*nod+1])arb[nod]=arb[2*nod];
		else arb[nod]=arb[2*nod+1];
   }
}
	
void construire(int nod,int st, int dr)
{if(st==dr){if(st==1)arb[nod]=0;
               else arb[nod]=infin;
            pret[st]=infin;
			}
	else{
		int m;
		m=(st+dr)/2;
		construire(nod*2,st,m);
	    construire(nod*2+1,m+1,dr);
		if(arb[2*nod]<arb[2*nod+1])arb[nod]=arb[2*nod];
		 else arb[nod]=arb[2*nod+1];
		
		}
}
		
int minim(int nod, int st,int dr)
{if(st==dr)return st;
  else
  { 
	  int m;
	  m=(st+dr)/2;
	  if(arb[2*nod]<arb[2*nod+1])return minim(2*nod,st,m);
	     else return minim(2*nod+1,m+1,dr);
  }
}

int main()
{
	int i;
	
	fin>>n;
	fin>>mm;
	for(i=1;i<=mm;i++)
	{	
		int x;
		muchie y;
		fin>>x>>y.inf>>y.cost;
		lv[x].push_back(y);
		
	}
	
	int j;
	
    construire(1,1,n);
	while(arb[1]!=infin)
	{
		 int cine,cat;
		 cine=minim(1,1,n);
		 pret[cine]=arb[1];
		 v[cine]=1;
		 cat=lv[cine].size();
		 for(i=0;i<cat;i++)
		 {
		 
			 if(!v[lv[cine][i].inf]&&pret[cine]+lv[cine][i].cost<pret[lv[cine][i].inf])
			 {
				 pret[lv[cine][i].inf]=pret[cine]+lv[cine][i].cost;
				 actualizare(1,1,n,lv[cine][i].inf,pret[lv[cine][i].inf]);
			 }
		 }
		 actualizare(1,1,n,cine,infin);
	 }
	 
	 for(i=2;i<=n;i++)
		{if(pret[i]!=infin)fout<<pret[i]<<" ";
	       else fout<<"0 ";
		}
		
		 
	
	return 0;
}