#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
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 <bool> vizitat;
vector <unsigned int> cost;
int n, m, s = 1;
nod_g temp;

void citire(){
    f >> n >> m;
    graf.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(){
    queue<int> coada;
    vector<nod_g>::iterator it;
    int primul = s;
    vizitat.resize(n+1);
    cost.resize(n+1, inf);
    vizitat[s] = 1;
    cost[s] = 0;
    coada.push(s);

    while(!coada.empty()){
        for(it = graf[primul].begin(); it != graf[primul].end(); ++it){
            if(!vizitat[it->nod]){
                vizitat[it->nod] = 1;
                coada.push(it->nod);
                if(cost[it->nod] > cost[primul] + it->cost) cost[it->nod] = cost[primul] + it->cost;
            }
        }
        coada.pop();
        primul = coada.front();
    }
}

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

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

    return 0;
}