#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <cstring>
#include <iterator>
#include <queue>
#include <limits.h>
using namespace std;

const int nMax = 50005;

int n, m;
vector <pair<int,int>> muchii[nMax];
int drum[nMax];
bool inCoada[nMax];

queue <int> coada;
void calculare(){

    int vecin, drumLaVecin;

    while(!coada.empty()){

        int nod = coada.front();
        coada.pop();
        inCoada[nod] = false;
       // 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 << vecin << " " << drumLaVecin << " " << drum[vecin] << "\n";
            if(drumLaVecin < drum[vecin]){
                drum[vecin] = drumLaVecin;
                if(inCoada[vecin] == false){
                    coada.push(vecin);
                    inCoada[vecin] = true;
                }
            }

        }

    }
}

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

    for(int i = 1; i < nMax; ++i)
        drum[i] = 20000000;

    drum[1] = 0;
    coada.push(1);

    calculare();

    for(int i = 2; i <= n; ++i){
        if(drum[i] == 20000000)
            drum[i] = 0;

        fout << drum[i] << " ";
    }

    return 0;
}