//
// Created by Cristian Stern on 5/19/2019.
//
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define oo 0x3f3f3f3f

using namespace std;

int main(){
    int n, m, x, y, cost;

    //ifstream f("E:\\FMI\\AG\\lab3\\date.in");
    //ofstream g("E:\\FMI\\AG\\lab3\\date.out");


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

    f>>n>>m;
    vector<vector<pair< int, int> > > G(n + 1);
    vector < int > d(n + 1, oo);
    //vector < int > t(n + 1, 0);
    set<pair<int, int>> S;
    for(int i = 0;i < m;i++){
        f>>x>>y>>cost;
        G[x].push_back(make_pair(cost, y));
    }
    int st = 1;
    d[st] = 0;
    S.insert(make_pair(d[st], st));
    while(!S.empty()){
        pair < int, int > u = *(S.begin());
        S.erase(S.begin());
        for(auto v : G[u.second]){
            if(d[v.second] > d[u.second] + v.first){    //relaxare
                d[v.second] = d[u.second] + v.first;
                //t[v.second] = u.second;
                S.insert(make_pair(d[v.second], v.second));
            }
        }
    }
    for(int i = 2;i <= n;i++){
        if(d[i] != oo)
            g<<d[i]<<" ";
        else g<<0<<" ";
    }

}