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

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

class Graph {
  private:
    int n;
    vector<vector<pair<int, int>>> ad;

  public:
    Graph(int n) :
        n(n), ad(n + 1) { }

    void addEdge(int x, int y, int z) {
        ad[x].emplace_back(y, z);
    }

    vector<int> bellman(int src) {
        vector<int> dp(n + 1, 1e9);
        dp[src] = 0;
        vector<int> cnt(n + 1);

        queue<int> q; q.push(src);
        while (!q.empty()) {
            int node = q.front(); q.pop();
            for (auto nghb : ad[node])
                if (dp[node] + nghb.second < dp[nghb.first]) {
                    dp[nghb.first] = dp[node] + nghb.second;
                    q.push(nghb.first);
                    if (++cnt[nghb.first] == n)
                        return vector<int>();
                }
        }
        return dp;
    }
};

int main() {
    int n, m; fin >> n >> m;
    Graph graph(n);
    for (int i = 0; i < m; i++) {
        int x, y, z; fin >> x >> y >> z;
        graph.addEdge(x, y, z);
    }

    auto ans = graph.bellman(1);
    for (int i = 2; i <= n; i++)
        fout << ans[i] << ' ';
    fout << '\n';

    fout.close();
}