#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 coada[MMAX],D[NMAX];
int n,m;
struct lista
{
    int v;
    int c;
    lista *urm;
};
lista *cap[NMAX],*nou;
void dijkstra(int ns)
{
    int i,pi,ps,nod,v,c;
    for(i=1;i<=n;i++)
        D[i]=inf;
    D[ns]=0;
    coada[1]=ns;
    pi=1;ps=1;
    while(pi<=ps)
    {
        nod=coada[pi];
        nou=cap[nod];
        while(nou!=NULL)
        {
            v=nou->v;
            c=nou->c;
            if(D[v]>D[nod]+c)
            {
                D[v]=D[nod]+c;
                ps++;
                coada[ps]=v;
            }
            nou=nou->urm;

        }
        pi++;
    }
}

int main()
 { int i,a,b,c;
    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;
    }
    in.close();
   /*for(i=1;i<=n;i++)
    {
        nou=cap[i];
        out<<"Lista de vecini a lui "<<i<<" este=";
        while(nou!=NULL)
        {
            out<<nou->v<<" ";
            nou=nou->urm;
        }
        out<<endl;

    }*/
    dijkstra(1);
    for(i=2;i<=n;i++)

        if(D[i]!=inf) out<<D[i]<<" ";
        else out<<"0 ";


    out.close();
    return 0;
}