#include <cstdio>
#include <vector>
#define NMAX 50010
#define INF 1999999999
using namespace std;

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

int cmin[NMAX];
int sol[NMAX], n, m, poz[NMAX];//pozitia unui varf in heap-ul cmin
int nrcmin;
bool Z[NMAX];//multimea varfurilor selectate la un moment dat

void citire();
void rez();
void afisare();
inline void build_heap();
void combinare (int[], int, int);
int get_min (int[], int &);
void insert_heap (int[], int, int);


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

void citire()
{
    int i, a, b, c;
    struct pack aux;
    FILE*fin=fopen ("dijkstra.in", "r");
    fscanf(fin, "%d %d", &n, &m);
    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, ct;
    int vfmin;
    build_heap(); //creez heap-ul initial

    while (nrcmin)
    {
        //selectez cel mai apropiat nod
        vfmin=get_min(cmin, nrcmin);
        Z[vfmin]=true;
        for (i=0; i<L[vfmin].size(); ++i)
        {
            if (!Z[L[vfmin][i].vf] && sol[L[vfmin][i].vf]>sol[vfmin]+L[vfmin][i].cost)
            {
                sol[L[vfmin][i].vf]=sol[vfmin]+L[vfmin][i].cost;
                //verific daca aveam sau nu varful deja in heap
                if (!poz[L[vfmin][i].vf])//nu aveam varful, il inserez
                {
                    ++nrcmin; cmin[nrcmin]=L[vfmin][i].vf;
                    insert_heap (cmin, nrcmin, nrcmin);
                }
                    else
                    insert_heap (cmin, nrcmin, poz[L[vfmin][i].vf]);

            }
        }
    }
}

inline void build_heap()
{
    int i, ct, lg;
    for (i=2; i<=n; ++i) sol[i]=INF;
    Z[1]=true;

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

    for (i=nrcmin/2; i; --i)
        combinare (cmin, nrcmin, i);//pun datele din cmin in ordinea lor
    return;
}

void combinare (int cmin[], int nrcmin, int tata)
{
    //cmin este un min-heap
    int val=sol[cmin[tata]], fiu=2*tata, varf=cmin[tata];
    while (fiu<=nrcmin)
    {
        if (fiu<nrcmin && 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]]=tata;
            tata=fiu;
            fiu=2*fiu;
        }
            else
            break;//atunci totul este acolo unde trebuie sa fie
    }
    cmin[tata]=varf;
    poz[varf]=tata;
    return;
}

int get_min (int cmin[], int &nrcmin)
{
    int rez;
    rez=cmin[1];
    cmin[1]=cmin[nrcmin--];
    combinare (cmin, nrcmin, 1);
    return rez;
}

void insert_heap (int cmin[], int nrcmin, int rad)
{
    int tata, fiu, varf=cmin[rad];
    fiu=rad; tata=fiu/2;
    while (tata && sol[cmin[tata]]>sol[varf])
    {
        cmin[fiu]=cmin[tata]; poz[cmin[tata]]=fiu;
        fiu=tata; tata=fiu/2;
    }
    cmin[fiu]=varf;
    poz[varf]=fiu;
}

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