#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

struct node {
    int next, val;
    bool operator>(const node& other) const {
        return val > other.val;
    }
};

priority_queue<node, vector<node>, greater<node>> Q;
int dp[50100];
vector<vector<node>> gr(50100);

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 2; i <= n; i++) {
        dp[i] = 1000000000;
    }

    for (int i = 0; i < m; i++) {
        int a, b, val;
        cin >> a >> b >> val;
        gr[a].push_back({b, val});
    }

    dp[1] = 0;
    Q.push({1, 0});

    while (!Q.empty()) {
        node now = Q.top();
        Q.pop();
        if (now.val != dp[now.next]) continue;
        for (auto &x : gr[now.next]) {
            if (dp[x.next] > dp[now.next] + x.val) {
                dp[x.next] = dp[now.next] + x.val;
                Q.push({x.next, dp[x.next]});
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (dp[i] == 1000000000) {
            cout << 0 << " ";
        } else {
            cout << dp[i] << " ";
        }
    }

    return 0;
}