#include <iostream>
#include <fstream>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int inf=1<<30;
const int NMAX=50001;
const int MMAX=250001;
int n,m,coada[MMAX],D[NMAX];
struct lista
{ int v;
    int c;
    lista *urm;
};
lista *cap[NMAX],*nou;
void dj( int ns)
{ int i,pi=1,ps=1;
    for(i=1;i<=n;i++)
        D[i]=inf;
D[ns]=0;
    coada[1]=ns;
    while(pi<=ps)
    {  nou=cap[coada[pi]];
          while(nou!=NULL)
               {
              if(D[nou->v]>D[coada[pi]]+nou->c)
               {     D[nou->v]=D[coada[pi]]+nou->c;
                                    ps++;coada[ps]=nou->v;} nou=nou->urm;}



        pi++;

    }



}



int main()
{ in>>n>>m; int a,b,c,i;
for(i=1;i<=m;i++)
    { in>>a>>b>>c;
        nou=new lista;
        nou->v=b;
        nou->c=c;
        nou->urm=cap[a];
        cap[a]=nou;
         }

     /* for(i=1;i<=n;i++)
      { nou=cap[i]; out<<i<<" ";
        while(nou!=NULL)
        {   out<<nou->v;
            nou=nou->urm;}
        out<<"\n"; } */
dj(1);
for(i=2;i<=n;i++)
    if(D[i]!=inf)out<<D[i]<<" ";
    else out<<"0 ";
    return 0;
}