#include <fstream>

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int Nmax=50000;
const int Mmax=250000;
const int inf=9999999;
int n,m,d[Nmax],coada[Mmax],nod,viz[Nmax];
struct lista
{   int v;
    int c;
    lista *urm;

};

lista *cap[Nmax],*nou;
void dijkstra(int ns)
{   int i,ps,pf,v,c;
    for(i=1;i<=n;i++)
        d[i]=inf;
    ps=1;
    pf=1;

    d[ns]=0;
    coada[1]=ns;
    while(ps<=pf)
    {   nod=coada[ps]; nou=cap[nod];
        while(nou)
        {  c=nou->c;
            v=nou->v;

            if(d[v]>c+d[nod])
            {   d[v]=c+d[nod];
                pf++;
                coada[pf]=v;

            }
        nou=nou->urm;
        }
        ps++;
    }

}
int main()
{   int i,a,b,c;

    in>>n>>m;
    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;

    }

    dijkstra(1);
    for(i=2;i<=n;i++)
    if(d[i]==inf) out<<0<<" ";
    else out<<d[i]<<" ";
    return 0;
}