#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{

short val;
short 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];

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);


        if(curent.dest == n){
             reinit_heap_propriu();
             return curent.val;
        }


        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);


        }

    }


    reinit_heap_propriu();
    return 0;
}

priority_queue <data> heap;

void reinit_heap(){

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

}


int dijkstra_heap(int n){

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

    heap.push(adaugare);

    while(!heap.empty()){

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


        if(curent.dest == n){
            reinit_heap();
            return curent.val;
        }


        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.push(adaugare);


        }

    }
    reinit_heap();
    return 0;
}


int main()
{
    //Citire vector

   short 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

    for(i=2;i<=n;i++){

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


    }


    return 0;
}