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

using namespace std;

int main(){
    int n, m, x, y, cost;
    //ifstream f("E:\\FMI\\AG\\lab3\\date.in");
    ofstream g("dijkstra.out");
    ifstream f("dijkstra.in");
    f>>n>>m;
    priority_queue <pair< int, int >> pq;
    vector<vector<pair< int, int> > > G(n + 1);
    vector < int > d(n + 1, oo);
    vector < int > t(n + 1, 0);
    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;
    pq.push(make_pair(0, st));
    while(!pq.empty()){
        pair < int, int> u = pq.top();
        pq.pop();
        for(auto v : G[u.second]){
            if(d[v.second] > d[u.second] + v.first){
                d[v.second] = d[u.second] + v.first;
                t[v.second] = u.second;
                pq.push(make_pair(d[v.second], v.second));
            }
        }
    }
    for(int i = 2;i <= n; i++)
        if(d[i] == oo)
            g<<0<<" ";
        else g<<d[i]<<" ";
}