#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 50000;
const int INF = 1e9;

struct Edge {
    int v, cost;

    bool operator < (const Edge &other) const {
        return this-> cost > other.cost;
    }
};

int n, m;
int dist[MAX_N + 5];

vector<Edge> G[MAX_N + 5];
priority_queue<Edge> pq;

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

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

    while (!pq.empty()) {
        auto u = pq.top();
        pq.pop();

        if (dist[u.v] != u.cost)
            continue;

        for (auto v : G[u.v])
            if (dist[v.v] > dist[u.v] + v.cost) {
                dist[v.v] = dist[u.v] + v.cost;
                pq.push({v.v, dist[v.v]});
            }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        G[a].push_back({b, c});
    }

    dijkstra(1);

    for (int i = 2; i <= n; i++)
        fout << dist[i] << ' ';
    return 0;
}