#include <fstream>
#include <bits/stdc++.h>
using namespace std;

#define INF 1<<30

int main(){
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int n, m, a, b, c;
    fin>>n>>m;
    unordered_map<int, unordered_map<int, int>> map;
    for(int i = 0; i < m; i++){
        fin>>a>>b>>c;
        map[a][b] = c;
    }

    // node + sum
    deque<pair<int, int>> deq;
    vector<int> v(n, INF);
    int node, sum, val, next;
    deq.push_back({1, 0});
    while(!deq.empty()){
        node = deq.front().first, sum = deq.front().second;
        deq.pop_front();
        for(auto h : map[node]){
            next = h.first, val = h.second;
            if(sum + val < v[next-1])
                v[next-1] = sum + val;
            deq.push_back({next, sum + val});
        }
    }

    for(int i = 1; i < n; i++){
        if(v[i] == INF)
            cout<<"0 ";
        fout<<v[i]<<" ";
    }

    return 0;
}