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

int v[50002];
struct muchie
{
    int inf;
    int cost;
}y;
     
vector <muchie> lv[50002];
int pret[50002];
int h[132000];
int n,m;
 
 
void actualizare(int nod,int st,int dr,int x,int cost){
	if(st==dr)h[nod]=cost;
	else{
    int mij;
    mij=(st+dr)/2;
    if(x<=mij)actualizare(2*nod,st,mij,x,cost);
       else actualizare(2*nod+1,mij+1,dr,x,cost);
     if(h[2*nod]<h[2*nod+1])h[nod]=h[2*nod];
        else h[nod]=h[2*nod+1];
   }
}
     
void construire(int nod,int st, int dr)
{if(st==dr){
	if(st==1)h[nod]=0;
	else h[nod]=infin;
	pret[st]=infin;
}
    else{
        int mij;
        mij=(st+dr)/2;
        construire(nod*2,st,mij);
        construire(nod*2+1,mij+1,dr);
        if(h[2*nod]<h[2*nod+1])h[nod]=h[2*nod];
		else h[nod]=h[2*nod+1];
         
        }
}
         
int minim(int nod, int st,int dr){
if(st==dr)return st;
  else{
     int m;
      m=(st+dr)/2;
      if(h[2*nod]<h[2*nod+1])return minim(2*nod,st,m);
		else return minim(2*nod+1,m+1,dr);
  }
}
 
int main()
{
	register int i;
    int x;
    ifstream f("dijkstra.in");
	ofstream g("dijkstra.out"); 
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y.inf>>y.cost;
        lv[x].push_back(y);     
    }
    construire(1,1,n);
    while(h[1]!=infin){
		 int cine;
         cine=minim(1,1,n);
         pret[cine]=h[1];
         v[cine]=1;
         for(i=0;i<lv[cine].size();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)g<<pret[i]<<" ";
		else g<<"0 ";
        }
    return 0;
}