#include <cstdio>
#include <vector>
#define NMAX 50001
#define INF 2000000
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

    for (ct=2; ct<=n; ++ct)
    {
        //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
                    insert_heap (cmin, nrcmin, L[vfmin][i].vf);
                    else
                    sol[L[vfmin][i].vf]=sol[vfmin]+L[vfmin][i].cost;
            }
        }
    }

}

inline void build_heap()
{
    int i, ct;
    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<=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]]=tata;
            tata=fiu;
            fiu=2*fiu;
        }
            else
            break;//atunci totul este acolo unde trebuie sa fie
    }
    cmin[tata]=varf;
    poz[varf]=tata;
    return;
}

/*void combinare (int cmin[], int nrcmin, int tata)
{
    //combin subarborele cu radacina in rad
    int aux;
    int fiu;
    fiu=2*tata;
    if (fiu+1<=nrcmin && sol[cmin[fiu]]>sol[cmin[fiu+1]])
        ++fiu;
    while (fiu<=nrcmin && sol[cmin[tata]]>sol[cmin[fiu]])//POSIBIL KILLED BY SIGNAL 11
    {
        //interschimb
        aux=cmin[tata];
        cmin[tata]=cmin[fiu]; poz[cmin[fiu]]=tata;
        cmin[fiu]=aux; poz[aux]=fiu;

        tata=fiu;
        fiu=2*tata;
        if (fiu+1<=nrcmin && sol[cmin[fiu]]>sol[cmin[fiu+1]])
            ++fiu;
    }
    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 inf)
{
    int tata, fiu;
    //cmin[++nrcmin]=inf;
    fiu=nrcmin; tata=fiu/2;
    while (tata && sol[cmin[tata]]>sol[inf])
    {
        cmin[fiu]=cmin[tata];
        fiu=tata; tata=fiu/2;
    }
    cmin[fiu]=inf;
    poz[inf]=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);
}