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

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

const int val_max =20005;
bool verificat[50005];

struct data{

int val;
int dest;

}adaugare,nimic,curent;

struct nod{

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

}*radacina;

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

int dijkstra(int n){

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

    heap_Insert(adaugare,radacina);

    while(!heap_Is_Empty(radacina)){

        curent=heap_Remove(radacina);
        verificat[curent.dest]=1;

        if(curent.dest == n)
            break;

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

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

                heap_Insert(adaugare, radacina);
            }

        }

    }

    // Golire heap
    while(heap_Remove(radacina).val != val_max);


    return curent.val;
}


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

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

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

        //reinitializare verificat

        for(j=1;j<=n;j++)
            verificat[j]=0;


    }
    /*
    adaugare.val=1;
    heap_insert(adaugare,radacina);
    adaugare.val=2;
    heap_insert(adaugare,radacina);
    adaugare.val=7;
    heap_insert(adaugare,radacina);
    adaugare.val=102;
    heap_insert(adaugare,radacina);

    cout<<heap_remove(radacina).val<<" ";
    cout<<heap_remove(radacina).val<<" ";
    cout<<heap_remove(radacina).val<<" ";
    cout<<heap_remove(radacina).val<<" ";
*/


    return 0;
}