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

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

queue <int> coada;

void calculare(){

    int nod, vecin, drumLaVecin;
    while(!coada.empty()){

        nod = coada.front();
        coada.pop();

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

    }
}

int main(){
    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] = 20001;

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

    calculare();

    for(int i = 2; i <= n; ++i)
        fout << drum[i] << " ";

    return 0;
}