#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <cstring>
#include <iterator>
using namespace std;

const int nMax = 50005;
const int drumMax = 0x3f3f3f3f;
int n, m;
vector <pair<int,int>> muchii[nMax];
int drum[nMax];


set <pair<bool, int>> coada;
void calculare(){

    int vecin, drumLaVecin;

    while(!coada.empty()){

        int nod = coada.begin()->second;
        coada.erase(coada.begin());

        //cout << nod << "\n";

        for(unsigned int i = 0; i < muchii[nod].size(); ++i){

            vecin = muchii[nod][i].first;

            drumLaVecin = muchii[nod][i].second + drum[nod];

           //cout << drumLaVecin << " " << drum[vecin] <<"\n";

            if(drumLaVecin < drum[vecin]){

                if(drum[vecin] != drumMax)
                    coada.erase(coada.find(make_pair(0, vecin)));

                drum[vecin] = drumLaVecin;

                coada.insert(make_pair(0 ,vecin));
            }

        }
       // cout << "\n";

    }
}

int main(){
    //ifstream fin("taxe2.in");
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    fin >> n >> m;

    for(int i = 1; i <= m; ++i){
        int a, b, lg;
        fin >> a >> b >> lg;
        muchii[a].push_back(make_pair(b, lg));
    }

    memset(drum, drumMax, sizeof drum); //umplu sirul de sumMax

    drum[1] = 0;
    coada.insert(make_pair(0,1));

    calculare();

    for(int i = 2; i <= n; ++i){
        if(drum[i] == drumMax)
            fout << 0 << " ";
        else
            fout << drum[i] << " ";
    }

    return 0;
}