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

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

#define inf 500000000

struct nod_g{
    int nod, cost;
};

vector < vector<nod_g> > graf;
vector <unsigned int> cost;
vector <bool> isIn;
int n, m, s = 1;
nod_g temp;

void citire(){
    f >> n >> m;
    graf.resize(n+1);
    isIn.resize(n+1);

    int x, y, c;
    for(int i = 1; i <= m; ++i){
        f >> x >> y >> c;
        temp.nod = y; temp.cost = c;
        graf[x].push_back(temp);
    }
    f.close();
}

void dijkstra(){
    multiset<int> coada;
    vector<nod_g>::iterator it;
    int primul = s;
    cost.resize(n+1, inf);
    cost[s] = 0;
    isIn[s] = 1;
    coada.insert(s);

    while(!coada.empty()){
        primul = *coada.begin();
        coada.erase( coada.begin() );
        isIn[primul] = false;

        for(it = graf[primul].begin(); it != graf[primul].end(); ++it){
            if(cost[it->nod] > cost[primul] + it->cost){
                if(isIn[it->nod])
                    coada.erase( it->nod );
                else isIn[it->nod] = true;
                coada.insert(it->nod);
                cost[it->nod] = cost[primul] + it->cost;
            }
        }
    }
}

void afisare(){
    for(int i = 1; i <= n; ++i){
        if(i == s) continue;
        if(cost[i] == inf) g << "0 ";
        else g << cost[i] << " ";
    }
    g.close();
}

int main(){
    citire();
    dijkstra();
    afisare();

    return 0;
}