#include <fstream>

using namespace std;

struct nod
{
    int urm,cost;
    nod *adr;
};

typedef nod *lda1;

lda1 lda[50005];

struct cel
{
    int val,nod;
} heap [250005];

int n,m,x,y,z,mheap,minim[50005];

void adauga(int val,int nod)
{
    ++mheap; heap[mheap].val=val; heap[mheap].nod=nod;

    while (mheap>1 && heap[mheap/2].val>val)
    {
        cel a=heap[mheap/2]; heap[mheap/2]=heap[mheap]; heap[mheap]=a;
    }
}

void scoate()
{
    heap[1]=heap[mheap];
    --mheap;
    int advr=1,mini=1,i=1;
    while (advr==1)
    {
        if (i*2<=mheap && heap[mini].val>heap[i*2].val) mini=i*2;
        if (i*2+1<=mheap && heap[mini].val>heap[i*2+1].val) mini=i*2+1;
        if (mini!=i) { cel p=heap[mini]; heap[mini]=heap[i]; heap[i]=p; i=mini; } else advr=0;
    }
}

int main()
{
    ifstream in ("dijkstra.in");
    ofstream out ("dijkstra.out");

    in>>n>>m;
    for (int i=1;i<=m;++i)
    {
        in>>x>>y>>z;
        lda1 p=new nod;
        p->urm=y;
        p->cost=z;
        p->adr=lda[x];
        lda[x]=p;
    }

    for (lda1 p=lda[1];p!=0;p=p->adr)
    {
        adauga(p->cost,p->urm);
    }
    for (int i=1;i<=n;++i) minim[i]=-1;
    while (mheap>0)
    {
        if (minim[heap[1].nod]==-1)
        {
            minim[heap[1].nod]=heap[1].val;
            for (lda1 p=lda[heap[1].nod];p!=0;p=p->adr)
            {
                adauga(heap[1].val+p->cost,p->urm);
            }
        }
        scoate();
    }

    for (int i=2;i<=n;++i) out<<minim[i]<<" ";

    in.close();
    out.close();
    return 0;
}