#include <fstream>
#include <list>
#include <string.h>
using namespace std;
ifstream f1("dijkstra.in");
ofstream f2("dijkstra.out");
#define N 50*1001
#define INF 2000000002

struct varf
{
    int nr, cost;
};

class Graf
{
    int mN, mM;
    list<varf> mVecin[N];

public:
    void read();
    int get_N() { return mN; }
    friend void dijkstra();
};

class Heap
{
    int mN;
    varf mAnsamblu[N];
    int mPoz[N];

    void moveup(int p, int ind);
    void movedown(int p, int ind);

public:
    void add(int x, int ind);
    int extract();
    void modify(int new_v,int ind);

    bool empty() { if (!mN) return 1; return 0; }
};

void Graf::read()
{
    f1>>mN>>mM;

    for (int i=1; i<=mM; i++)
    {
        int a;
        varf m;
        f1>>a>>m.nr>>m.cost;

        mVecin[a].push_back(m);
    }
}

void Heap::moveup(int p, int ind)
{
    while ( p > 1 && mAnsamblu[p/2].cost > mAnsamblu[p].cost )
    {
        swap( mAnsamblu[p/2], mAnsamblu[p] );
        swap( mPoz[ p/2 ], mPoz[ p ] );
        p/=2;
    }
    mPoz[ind]= p;
}

void Heap::movedown(int p, int ind)
{
    while ( p*2 <= mN  &&  mAnsamblu[p].cost > min(mAnsamblu[p*2].cost, mAnsamblu[p*2+1].cost ) )
        if ( mAnsamblu[p*2].cost <= mAnsamblu[p*2+1].cost )
        {
            swap( mAnsamblu[p*2],  mAnsamblu[p] );
            p*= 2;
        }
        else
        if ( p*2+1 <= mN )
        {
            swap( mAnsamblu[p*2+1],  mAnsamblu[p] );
            p= p*2+1;;
        }

    mPoz[ind]= p;
}

void Heap::add(int x, int ind)
{
    mAnsamblu[++mN].cost= x;
    mAnsamblu[mN].nr= ind;

    moveup( mN , ind );
}

int Heap::extract()
{
    int x= mAnsamblu[1].nr;

    mAnsamblu[1]= mAnsamblu[mN--];

    movedown(1, mAnsamblu[1].nr );

    return x;
}

void Heap::modify(int new_v, int ind)   // ind e varful din graf
{
    int p= mPoz[ind];
    mAnsamblu[ p ].cost= new_v;


    moveup(p, ind);         // pt ca e mai simplu ))
    movedown(p, ind);
}


Heap h;
Graf g;
int DistMin[N];
bool used[N];

void dijkstra()
{
    int nod;

    memset( DistMin, INF, sizeof(DistMin) );

    h.add(0, 1);
    for (int i=2; i<= g.mN ; i++)
        h.add(INF , i );

    DistMin[1]= 0;

    while ( !h.empty() )
    {
        nod= h.extract();
        used[nod]=1;

        for ( list<varf>::iterator it= g.mVecin[nod].begin(); it != g.mVecin[nod].end(); it++ )
            if ( DistMin[nod] + it->cost < DistMin[ it->nr ] )
            {
                DistMin[ it->nr ]= DistMin[nod] + it->cost;
                h.modify(DistMin[ it->nr ], it->nr );
            }
    }
}

int main()
{
    g.read();
    dijkstra();

    for (int i=2; i<= g.get_N() ; i++)
        f2<<DistMin[i]<<" ";

    f2.close();
    return 0;
}