#include <fstream>
#define INF 2000000
#define NMAX 50001
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct Arc {int vf; int c;};

int n, x0;
Arc G[15001][15001];
int dmin[NMAX];//distantele minime
int prec[NMAX];//pot reconstitui drumul
int M[NMAX];//multimea vf selectate
int h[NMAX], lgh;//in h sunt vf organiate ca min-heap
int poz[NMAX];//poz[i]=-1 daca vf i nu a fost pus in heap, respectiv 1 daca e pus in heap

void citire();
void afisare();
void dijkstra();
void InsertHeap(int vf);
void Upgrade(int fiu);
int ExtractMin();
void adauga_arc(int x, int y, int cost);

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

void citire()
{
    int i, m, x, y, cost;
    fin>>n>>m; x0=1;
    for(i=0;i<m;i++)
    {
        fin>>x>>y>>cost;
        adauga_arc(x, y, cost);
    }
}

void adauga_arc(int x, int y, int cost)
{
    G[x][0].vf++;
    G[x][G[x][0].vf].c=cost;
    G[x][G[x][0].vf].vf=y;
}

void dijkstra()
{
    int vfmin, i, j, nrs=1;
    for(i=1;i<=n;i++)
    {
        dmin[i]=INF; prec[i]=x0; poz[i]=-1;
    }
    //x0 intra in heap pe poz 1
    dmin[x0]=0; prec[x0]=-1; poz[x0]=1; h[1]=x0; lgh=1;
    while(nrs<n)
    {
        vfmin=ExtractMin();
        M[vfmin]=1; nrs++;
        //parcurg lista de adiacenta a lui vfmin
        for(j=1;j<=G[vfmin][0].vf;j++)
            if(!M[G[vfmin][j].vf])//nu a fost deja selectat
                if(dmin[G[vfmin][j].vf]>dmin[vfmin]+G[vfmin][j].c)
                {
                    dmin[G[vfmin][j].vf]=dmin[vfmin]+G[vfmin][j].c;
                    prec[G[vfmin][j].vf]=vfmin;
                    if(poz[G[vfmin][j].vf]==-1)//acest vecin nu e selectat
                        InsertHeap(G[vfmin][j].vf);
                    else
                        Upgrade(poz[G[vfmin][j].vf]); //il promovez
                }
    }
}

void Upgrade(int fiu)
{
    int tata=fiu/2,aux;
    while(tata && dmin[tata]>dmin[fiu])
    {
        poz[h[fiu]]=tata; poz[h[tata]]=fiu;
        aux=h[fiu]; h[fiu]=h[tata]; h[tata]=aux;
        fiu=tata;
        tata=fiu/2;
    }
}

void InsertHeap(int vf)
{
    h[++lgh]=vf;
    poz[vf]=lgh;
    Upgrade(lgh);
}

int ExtractMin()
{
    int fiu,tata,aux;
    int minim=h[1];
    h[1]=h[lgh--]; poz[h[1]]=-1;
    //downgrade
    tata=1; fiu=2*tata;
    while(fiu<=lgh)
    {
        if(fiu<lgh&&dmin[h[fiu]]>dmin[h[fiu+1]]) fiu++;
        if(dmin[h[tata]]>dmin[h[fiu]])
        {
            poz[h[fiu]]=tata; poz[h[tata]]=fiu;
            aux=h[fiu]; h[fiu]=h[tata]; h[tata]=aux;
            tata=fiu;
            fiu=2*tata;
        }
        else break;
    }
    return minim;
}

void afisare()
{
    int i;
    for(i=2;i<=n;i++)
    {
        if(dmin[i]==INF)
            fout<<0<<' ';
        else
            fout<<dmin[i]<<' ';
    }
    fout<<'\n';
    fout.close();
}