#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];

struct cmp{
    bool operator()(int x, int y){
        return drum[x] > drum[y];
    }

};

priority_queue <int, vector<int>, cmp> coada;

void calculare(){

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

    int vecin, drumLaVecin, nod;

    while(!coada.empty()){

        nod = coada.top();
        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];

            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;

    calculare();

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

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

    return 0;
}