#include <bits/stdc++.h>
#define Nmax 50050
#define INF (1 << 30)

using namespace std;

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

int N, dp[Nmax];
vector < pair < int, int > > L[Nmax];
priority_queue <pair <int, int> > q;
bool used[Nmax];

inline void Read() {
    int i, M, x, y, c;
    fin >> N >> M;
    for (i = 1; i <= M; i++) {
        fin >> x >> y >> c;
        L[x].push_back({y, c});
    }
    fin.close();
}

inline void Solve() {
    int i, cost, node, newNode;
    for (i = 2; i <= N; i++)
        dp[i] = INF;
    dp[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        node = q.top().second;
        q.pop();
        if (!used[node]) {
            used[node] = 1;
            for (auto it : L[node]) {
                newNode = it.first;
                cost = it.second;
                if (dp[newNode] > dp[node] + cost) {
                    dp[newNode] = dp[node] + cost;
                    q.push({-dp[newNode], newNode});
                }
            }
        }
    }
}

inline void Write() {
    int i;
    for (i = 2; i <= N; i++)
        if (dp[i] == INF) fout << "0 ";
        else fout << dp[i] << " ";
    fout << "\n";
    fout.close();
}

int main() {
    Read();
    Solve();
    Write();
    return 0;
}