#include <bits/stdc++.h>
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

const int NMAX = 50005;

int n, m;
vector <pair<int, int>> G[NMAX];
int dist[NMAX];

void dijkstra() {
    for (int i = 1; i <= n; i++)
        dist[i] = 1e9 + 5;

    priority_queue <pair<int, int>> Q;

    Q.push({0, 1});
    dist[1] = 0;

    while (!Q.empty()) {
        int nod = Q.top().second;
        Q.pop();

        for (auto v: G[nod])
            if (dist[nod] + v.second < dist[v.first]) {
                dist[v.first] = dist[nod] + v.second;
                Q.push({-dist[v.first], v.first});
            }
    }
}

int main()
{
    fi >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, c; fi >> u >> v >> c;
        G[u].push_back({v, c});
    }

    dijkstra();

    for (int i = 2; i <= n; i++)
        fo << dist[i] << " ";

    return 0;
}