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

const int nMax = 50005, drumMax = 20001;
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());

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

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

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

            drum[vecin] = min(drumLaVecin, drum[vecin]);

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

        }
        muchii[nod].clear();

    }
}

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] == 20001)
            fout << 0 << " ";
        else
            fout << drum[i] << " ";
    }

    return 0;
}