#include <iostream>
#include <fstream>
using namespace std;
ifstream in ("dijkstra.in");
ofstream out("dijkstra.out");
const int inf=1<<30;
const int MMAX=250001;
const int NMAX=50001;
struct lista
{ int v;
   int c;
    lista *urm;
};
lista *cap[NMAX],*nou;
int coada[MMAX],D[NMAX];
int n,m;
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)
                {if(D[nou->v]>D[coada[pi]]+nou->c)
                {ps++;D[nou->v]=D[coada[pi]]+nou->c;
                    coada[ps]=nou->v;
              }  nou=nou->urm;

             }

             pi++;
              }
        }
int main()
{ int a,b,c,i;
    in>>n>>m;
    for(i=1;i<=n;i++)
        cap[i]=NULL;
    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;
        }
        dj(1);
/*for(i=1;i<=n;i++)
{ nou=cap[i];
    while(nou)
    {out<<nou->v<<" ";
        nou=nou->urm; }
    out<<endl;
    }
*/
for(i=2;i<=n;i++)
   if(D[i]!=inf)out<<D[i]<<" ";
   else out<<"0 ";
    return 0;
}