#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[pi]=ns;
        while(pi<=ps)
        { nou=cap[pi];
            while(nou)
             {if(D[nou->v]>D[pi]+nou->c)
                {D[nou->v]=D[pi]+nou->c;
                    coada[ps]=nou->v;
             ps++; }  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++)
    out<<D[i]<<" ";
    return 0;
}