#include <bits/stdc++.h>
#define Nmax 100005
#define pi pair<int, int>
#define INF INT_MAX
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int N, M;
vector<pi> G[Nmax];
priority_queue<pi, vector<pi>, greater<pi> > Q;
bool vis[Nmax];
int dp[Nmax];
int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int x, y, c;
        f >> x >> y >> c;
        G[x].push_back({y, c});
    }

    for (int i = 2; i <= N; ++i)
        dp[i] = INF;

    Q.push({0, 1});
    while (!Q.empty()) {
        int node = Q.top().second;
        int dist = Q.top().first;
        Q.pop();

        if (vis[node] == 0) {
        vis[node] = 1;
        for (auto it: G[node]) {
            int dist2 = dist + it.second;
            int node2 = it.first;
            if (dist2 < dp[node2] && !vis[node2])
                    Q.push({dist2, node2}), dp[node2] = dist2;
            }
        }}

    for (int i = 2; i <= N; ++i)
       if (dp[i] == INF) g << 0 << " " ;
       else  g << dp[i] << " ";

    return 0;
}