#include <cstdio>
#include <vector>
#define MAXN 50000
#define MAXM 250000
using namespace std;
int rez[MAXN+1];
class Muchie{
 public :
   int nod;
   int cost;
};
vector <Muchie> G[MAXN+1];
class Heap{
 public :
   int drum;
   int nod;
};
Heap H[MAXM+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;
}
inline void myswap(int x,int y){
    Heap aux=H[x];
    H[x]=H[y];
    H[y]=aux;
}
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;
    }
}
void Dijkstra(int n){
    int nrnod,nh,nod;
    nrnod=1;
    nh=1;
    H[nh].drum=0;
    H[nh].nod=1;
    while(nrnod<=n){
       nod=H[1].nod;
       rez[nod]=H[1].drum;
       myswap(1,nh);
       nh--;
       coborare(1,nh);
       for(int i=0;i<G[nod].size();i++)
         if(G[nod][i].nod!=1&&rez[G[nod][i].nod]==0){
             nh++;
             H[nh].drum=rez[nod]+G[nod][i].cost;
             H[nh].nod=G[nod][i].nod;
             urcare(nh);
         }
       nrnod++;
    }
}
int main(){
   FILE*fi,*fout;
   int i,n,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(n);
   for(i=2;i<=n;i++)
     fprintf(fout,"%d " ,rez[i]);
   fclose(fi);
   fclose(fout);
   return 0;
}