#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int val_max =20005;

struct data{

int val;
int dest;

}adaugare,nimic,curent;

struct nod{

data val;
struct nod *dr;
struct nod *st;

}*radacina;

bool operator <(data a , data b){
    return a.val > b.val;
}

vector <data> v[50005];

int dist[50005];

void heap_Insert(data x , nod *&actual){

    if(actual == NULL){
        actual= new nod;
        actual->val= x;
        actual->st= NULL;
        actual->dr= NULL;
        return;
    }

    if(x.val < actual->val.val )
        swap(x,actual->val );


    if(actual->dr == NULL){
        heap_Insert(x , actual->dr );
        return;
    }


    if(actual->st == NULL){
        heap_Insert(x , actual->st );
        return;
    }


    if(actual->st->val.val < actual->dr->val.val)
        heap_Insert(x, actual->st);
    else
        heap_Insert(x, actual->dr);

}


data heap_Remove(nod *actual){

    nimic.val= val_max;

    if(actual == NULL)
        return nimic;

    data returnare= actual->val;
    int st;
    int dr;

    if(actual->st != NULL)
        st= actual->st->val.val;
    else
        st=val_max;

    if(actual->dr != NULL)
        dr= actual->dr->val.val;
    else
        dr= val_max;

    if(st<dr)
        actual->val= heap_Remove(actual->st);
    else
        actual->val= heap_Remove(actual->dr);

    return returnare;
}

bool heap_Is_Empty(nod *radacina){

    if(radacina == NULL)
        return true;

    if(radacina->val.val == val_max )
        return true;

    return false;
}

void reinit_heap_propriu(){

    while(heap_Remove(radacina).val != val_max);

}


int dijkstra(int n){

    adaugare.dest= 1;
    adaugare.val= 0;

    heap_Insert(adaugare,radacina);

    while(!heap_Is_Empty(radacina)){

        curent=heap_Remove(radacina);


        for(int i=0; i<v[curent.dest].size();i++ ){


            adaugare.val= curent.val + v[ curent.dest ][i].val;
            adaugare.dest= v[ curent.dest ][i].dest;

            heap_Insert(adaugare, radacina);


        }

    }

    return 0;
}

priority_queue <data> heap;

void reinit_heap(){

    while(!heap.empty())
        heap.pop();

}

void dijkstra_heap(int n){

    adaugare.dest= 1;
    adaugare.val= 0;

    heap.push(adaugare);

    while(!heap.empty()){

        curent=heap.top();
        heap.pop();

        if(dist[curent.dest] == 0)
            dist[curent.dest]=curent.val;

        for(int i=0; i<v[curent.dest].size();i++ )
            if( dist[ v[ curent.dest ][i].dest ] == 0 ){

                adaugare.val= curent.val + v[ curent.dest ][i].val;
                adaugare.dest= v[ curent.dest ][i].dest;

                heap.push(adaugare);
            }


    }
}


int main()
{
    //Citire vector

   int i,j,n,m,a,b,c;

    fin>>n>>m;

    for(i=0;i<m;i++){

        fin>>a>>b>>c;
        adaugare.val=c;
        adaugare.dest=b;

        v[a].push_back(adaugare);

    }

    //Dijkstra pentru n noduri


    dijkstra_heap(i);
    //fout<<dijkstra(i)<<" ";

    for(i=2;i<=n;i++)
        fout<<dist[i]<<" ";



    return 0;
}