#include <cstdio>
#include <vector>
#define MAXN 50000
#define INF 1000000000
int rez[MAXN+1];
class Muchie{
 public :
   int nod;
   int cost;
};
std::vector <Muchie> G[MAXN+1];
class Heap{
 public :
   int drum;
   int nod;
};
Heap H[MAXN+1];
inline int lson(int nod){
   return 2*nod;
}
inline int rson(int nod){
   return 2*nod+1;
}
inline int tata(int nod){
   return nod/2;
}
int poz[MAXN+1];
inline void myswap(int x,int y){
    Heap aux=H[x];
    H[x]=H[y];
    H[y]=aux;
    int p=poz[H[x].nod];
    poz[H[x].nod]=poz[H[y].nod];
    poz[H[y].nod]=p;
}
inline void urcare(int nod){
    while(tata(nod)>0&&H[nod].drum<H[tata(nod)].drum){
       myswap(nod,tata(nod));
       nod=tata(nod);
    }
}
inline void coborare(int nod,int nh){
    int flag=1,aux;
    while(flag==1){
        aux=nod;
        if(lson(nod)<=nh&&H[aux].drum>H[lson(nod)].drum)
          aux=lson(nod);
        if(rson(nod)<=nh&&H[aux].drum>H[rson(nod)].drum)
          aux=rson(nod);
        if(nod==aux)
          flag=0;
        myswap(nod,aux);
        nod=aux;
    }
}
int n;
void Dijkstra(){
    int nh,nod,drum,i;
    for(i=2;i<=n;i++)
       rez[i]=INF;
    nh=1;
    H[nh].drum=0;
    H[nh].nod=1;
    while(nh>0){
       nod=H[1].nod;
       drum=H[1].drum;
       myswap(1,nh);
       nh--;
       coborare(1,nh);
       for(i=0;i<G[nod].size();i++)
         if(rez[G[nod][i].nod]==INF){
             nh++;
             H[nh].drum=drum+G[nod][i].cost;
             H[nh].nod=G[nod][i].nod;
             rez[G[nod][i].nod]=drum+G[nod][i].cost;
             poz[G[nod][i].nod]=nh;
             urcare(nh);
         }
         else if(rez[G[nod][i].nod]>drum+G[nod][i].cost){
              rez[G[nod][i].nod]=drum+G[nod][i].cost;
              H[poz[G[nod][i].nod]].drum=drum+G[nod][i].cost;
              urcare(poz[G[nod][i].nod]);
         }
    }
}
int main(){
   FILE*fi,*fout;
   int i,m,a;
   fi=fopen("dijkstra.in" ,"r");
   fout=fopen("dijkstra.out" ,"w");
   fscanf(fi,"%d%d" ,&n,&m);
   for(i=0;i<m;i++){
      Muchie m;
      fscanf(fi,"%d%d%d" ,&a,&m.nod,&m.cost);
      G[a].push_back(m);
   }
   Dijkstra();
   for(i=2;i<=n;i++)
     fprintf(fout,"%d " ,rez[i]);
   fclose(fi);
   fclose(fout);
   return 0;
}