#include <fstream>
#include<vector>
#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;
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
vector <Arc>G[NMAX];

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)
{
    Arc a;
    a.vf=y; a.c=cost;
    G[x].push_back(a);
}

void dijkstra()
{
    int vfmin, i, j, nrs=0;
    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)
    {
        if(lgh>0)
        {
            vfmin=ExtractMin();
            M[vfmin]=1; nrs++;
            //parcurg lista de adiacenta a lui vfmin
            for(j=0;j<G[vfmin].size();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
                    }
        }
        else break;
    }
}

void Upgrade(int fiu)
{
    int tata=fiu/2, aux;
    while(tata&&dmin[h[tata]]>dmin[h[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();
}