#include <bits/stdc++.h>
#define Nmax 50005
#define INF 50000 * 20000
#define pi pair<int, int>
#define pb push_back
#define mp make_pair
using namespace std;

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

int N, M;
vector <pi> graph[Nmax];
priority_queue<pi, vector<pi>, greater<pi> >q;
bool done[Nmax];
int ans[Nmax];
int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int x, y, d;
        f >>x >> y >> d;
        graph[x].pb(mp(d, y));
    }

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

    q.push(mp(0, 1));
    while (!q.empty()) {
        int node = q.top().second;
        q.pop();

    if (done[node] == 0) {
        done[node] = 1;

        for (auto it: graph[node]) {
            int node2 = it.second;
            int dist2 = it.first + ans[node];

            if (dist2 < ans[node2]) {
                ans[node2] = dist2;
                q.push(mp(dist2, node2));
            }
        }
    }
    }

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

    return 0;
}