//se da un graf orientat cu n varfuri si m muchii
//sa se det lg minima a drumului de la nodul 1 la toate celelalte noduri si sa se afiseze aceste lungimi
#include <cstdio>
#include <vector>
#define NMAX 50010
#define INFINIT 199999999
using namespace std;

int sol[NMAX], poz[NMAX]; //poz[i]=pozitia in care se afla costul minim de la multimea Z la varful i in heap-ul cmin, daca acest vf nu este in Z
bool Z[NMAX];//multimea varfurilor deja selectate
int n, m, cn;

struct pack{
    int cost, vf;
};
vector <struct pack> L[NMAX];
int cmin[NMAX];

void citire();
void rez();
void afisare();
void Creare_Heap();
int Extrage_Min();
void Combinare (int, int);

int main()
{
    citire();
    rez();
    afisare();
    return 0;
}

void citire()
{
    FILE*fin=fopen ("dijkstra.in", "r");
    fscanf(fin, "%d %d", &n, &m);
    cn=n;
    int i, a, b, c;
    struct pack aux;
    for (i=1; i<=m; ++i)
    {
        fscanf(fin, "%d %d %d", &a, &b, &c);
        aux.vf=b; aux.cost=c;
        L[a].push_back (aux);
    }
    fclose(fin);
    return;
}

void rez()
{
    int i, vfcrt, ct, j;

    Creare_Heap();

    for (ct=2; ct<=cn; ++ct)
    {
        //caut acel varf care nu este in multimea Z si care se afla cel mai aproape de unul dintre varfurile care apartin acestei multimi
        vfcrt=Extrage_Min();//extrag varful cu costul minim din heap-ul cmin
        Z[vfcrt]=1;
        //verific daca ar putea schimba cmin-ul
        for (i=0; i<L[vfcrt].size(); ++i)
            if (sol[vfcrt]+L[vfcrt][i].cost<sol[L[vfcrt][i].vf] && !Z[L[vfcrt][i].vf])
        {
            sol[L[vfcrt][i].vf]=sol[vfcrt]+L[vfcrt][i].cost;
            if (!poz[L[vfcrt][i].vf])
            {
                cmin[++n]=L[vfcrt][i].vf;
                poz[L[vfcrt][i].vf]=n;
            }
            //cmin[ poz[L[vfcrt][i].vf] ].cost=sol[vfcrt]+L[vfcrt][i].cost;
            for (j=n/2; j; --j)
                Combinare (j, n);
        }
    }
    return;
}

void Creare_Heap()
{
    int i;
    struct pack aux;
    //selectez primul varf separat
    for (i=2; i<=cn; ++i)
        sol[i]=INFINIT;

    Z[1]=1; n=0;
    for (i=0; i<L[1].size(); ++i)
    {
        sol[L[1][i].vf]=L[1][i].cost;
        cmin[++n]=L[1][i].vf;
        poz[L[1][i].vf]=n;
    }

    for (i=n/2; i; --i)
        Combinare (i, n);
    return;
}

int Extrage_Min()
{
    int aux=cmin[1];
    cmin[1]=cmin[n];
    --n;
    Combinare (1, n);
    return aux;
}

void Combinare (int i, int n)
{
    //cmin este un min-heap
    int val=sol[cmin[i]], tata=i, fiu=2*i, varf=cmin[i];
    while (fiu<=n)
    {
        if (fiu<n && sol[cmin[fiu]]>sol[cmin[fiu+1]])//aleg minimul dintre fiul stang si fiul drept
            ++fiu;
        if (val>sol[cmin[fiu]])
        {
            cmin[tata]=cmin[fiu];
            poz[cmin[fiu]]=poz[cmin[tata]];
            tata=fiu;
            fiu=2*fiu;
        }
            else
            break;//atunci totul este acolo unde trebuie sa fie
    }
    cmin[tata]=varf;
    poz[varf]=tata;
    return;
}

void afisare()
{
    FILE*fout=fopen ("dijkstra.out", "w");
    int i;
    for (i=2; i<=cn; ++i)
    {
        if (sol[i]==INFINIT)
            sol[i]=0;
        fprintf(fout, "%d ", sol[i]);
    }
    fprintf(fout, "\n");
    fclose(fout);
    return;
}