#include<fstream>
using namespace std;

#define tata(k)  k/2
#define fiu_dr(k)  k*2+1
#define fiu_st(k)  k*2

const int maxn = 50001;
const int oo = 1<<30;

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

int H[maxn],N,k,d[maxn],poz[maxn];

struct graf
{   int nod,cost;
    graf *urm;
} *a[maxn];

void add(int where,int what,int cost)
{
    graf *g=new graf;
    g->nod=what;
    g->cost=cost;
    g->urm=a[where];
    a[where]=g;
}

void swap(int x,int y)
{
    int aux=H[x];
    H[x]=H[y];
    H[y]=aux;
}

void up(int kk)
{
    while(kk>1 && d[H[kk]]>d[H[tata(kk)]])
    {
        poz[H[kk]]=tata(kk);
        poz[tata(kk)]=kk;

        swap(tata(kk),kk);
        kk=tata(kk);
    }
}

void down(int kk)
{
    int fiu;
    do
    {
        fiu=0;
        if(fiu_st(kk)<=k)
        {
            fiu=fiu_st(kk);
            if(fiu_dr(kk)<=k && H[fiu]<H[fiu_dr(kk)])
                fiu=fiu_dr(kk);
        }
        if(H[fiu]<H[kk])
        {
            fiu=0;
        }
        if(fiu)
        {
            poz[H[k]]=fiu;
            poz[H[fiu]]=kk;

            swap(H[kk],H[fiu]);
            kk=fiu;
        }
    }while(fiu);
}

void solve()//dijkstra cu heap
{
    int i,min;
    graf *g;
    for(i=1;i<=N;++i)
    {
        d[i]=oo;
        poz[i]=-1;
    }

    d[1]=0;
    poz[1]=1;
    H[++k]=1;

    while(k)
    {
        min=H[1];
        swap(1,k);
        k--;

        poz[H[1]]=1;
        down(1);

        g=a[min];
        while(g)
        {
            if(d[min] + (g->cost) < d[g->nod])
                d[g->nod] = d[min] + (g->cost);
            if(poz[g->nod]!=-1)
                up(poz[g->nod]);
            else
            {
                H[++k]=g->nod;
                poz[H[k]]=k;
                up(k);
            }
            g=g->urm;
        }


    }


}

int main()
{
    int i,A,B,C,M;
    in>>N>>M;
    for(i=1;i<=N;++i)
    {
        in>>A>>B>>C;
        add(A,B,C);
    }
    solve();
    for(i=2;i<=N;++i)
    {
        if(d[i]==oo)
            out<<"0";
        else out<<d[i]<<" ";
    }
    out<<'\n';

    return 0;
}