#include <bits/stdc++.h>

using namespace std;
const int NMAX = 50100;

int N, M;
vector <int> ans;
priority_queue <pair <int, int>> heap;
vector <pair <int, int>> edges[NMAX];

void read(){
    scanf("%d%d", &N, &M);
    int x, y, c;
    for(int i = 1; i <= M; i++){
        scanf("%d%d%d", &x, &y, &c);
        edges[x].push_back(make_pair(y, c));
    }
    ans.resize(N + 1, 2e9);
}

void solve(pair <int, int> node){
    heap.push(node);
    ans[node.second] = 0;
    while(!heap.empty()){
        node = heap.top();
        heap.pop();
        if(ans[node.second] <= node.first)
            continue;
        for(auto it : edges[node.second]){
            if(ans[it.first] > node.first + it.second){
                ans[it.first] = node.first + it.second;
                heap.push(make_pair(node.first + it.second, it.first));
            }
        }
    }
}

int main() {

    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    read();
    solve(make_pair(0, 1));
    for(int i = 2; i < ans.size(); i++){
        if(ans[i] == 2e9)
            ans[i] = 0;
        printf("%d ", ans[i]);
    }

    return 0;
}