#include <bits/stdc++.h>
#define Nmax 50005
#define INF 2e9
using namespace std;

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

int N, M;
int dist[Nmax];
bool vis[Nmax];
vector<pair<int, int> > G[Nmax];
struct element{
    int node, cost;
    bool operator <(const element &x) const {
         return cost > x.cost;
    }
};
priority_queue<element> Q;

int main()
{
    fin >> N >> M;
    while (M--) {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back({y, c});
    }

    for (int i = 2; i <= N; ++i)
        dist[i] = INF;
    Q.push({1, 0});

    while (!Q.empty()) {
        int node = Q.top().node, len = Q.top().cost;
        Q.pop();
        if (vis[node]) continue;
        vis[node] = 1;
        for (auto it: G[node]) {
            int nxt = it.first, len2 = len + it.second;
            if (vis[nxt] == 0 && len2 < dist[nxt]) {
                 dist[nxt] = len2;
                 Q.push({nxt, len2});
            }
        }
    }

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

    return 0;
}