#include <iostream>
#include <vector>
#include <fstream>
#define NMAX 50010
#define MMAX 250010
#define inf 2100000000
#define pb push_back
#define mkp make_pair
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct arb{
int nod,val;
}heap[NMAX];

int n,m,lheap,poz[NMAX];//poz in heap
bool viz[NMAX];
int rasp[NMAX];

void introd_heap(int node,int valoare)
{
    lheap++;
    heap[lheap].nod=node;
    heap[lheap].val=valoare;
    poz[node]=lheap;//initializam in heap primul nod si retinem pozitia lui in heap
}

void upheap(int p,int valoare)
{
    int index=p;
    heap[index].val=valoare;

    while(index/2>=1 && heap[index].val<heap[index/2].val)
    {
        //urcam nodul cat mai sus cat timp este mai mic decat parintele
        swap(poz[heap[index].nod],poz[heap[index/2].nod]);
        swap(heap[index],heap[index/2]);
        index=index/2;
    }
}

void downHeap()
{
    int index=1;
    while(2*index<=lheap)
    {
        int minIndex=index;
        //stabilim minimul intre stanga si dreapta(daca exista)
        if(heap[2*index].val<heap[index].val)
        {
            minIndex=2*index;
        }
        if(2*index+1<=lheap && heap[2*index+1].val<heap[minIndex].val)
            minIndex=2*index+1;

        if(minIndex!=index)
        {
            swap(poz[heap[index].nod],poz[heap[minIndex].nod]);
            swap(heap[index],heap[minIndex]);
            index=minIndex;
        }
        else
            index=lheap*4;//stop
    }
}

arb getElimVarf()
{
    arb x=heap[1];
    poz[heap[lheap].nod]=1;
    //heap[1].nod=heap[lheap].nod;
    //heap[1].val=heap[lheap].val;
    swap(heap[1],heap[lheap]);
    lheap--;

    downHeap();

    return x;
}

vector <pair<int,int>> muc[NMAX];
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        muc[x].pb(mkp(y,c));
    }

    introd_heap(1,0);
    for(int i=2;i<=n;i++)
        introd_heap(i,inf);//initializam toate celelalte noduri in heap cu inf


    while(lheap>0 && heap[1].val!=inf)
    {
        arb xmin=getElimVarf();
        viz[xmin.nod]=1;
        rasp[xmin.nod]=xmin.val;//dist pana la nodul curent

        for(unsigned int i=0;i<muc[xmin.nod].size();i++)
        {
            int dest,newcost;
            dest=muc[xmin.nod][i].first;
            newcost=muc[xmin.nod][i].second;//muchia

            if(viz[dest]==0 && heap[poz[dest]].val>newcost+xmin.val)
                upheap(poz[dest],newcost+xmin.val);
        }
    }
    //fout<<cost<<'\n'<<n-1<<'\n';
    for(int i=2;i<=n;i++)
        fout<<rasp[i]<<' ';

    return 0;
}