#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 50005;
const int INF = 0x3f3f3f3f;

int n, m;
int dist[N_MAX];
vector < pair <int, int> > graph[N_MAX];

struct Heap {
    int node, cost;
    Heap(int n, int c) : node(n), cost(c) {}
    bool operator < (const Heap &other) const {
        return cost > other.cost;
    }
};
priority_queue<Heap> q;

void read() {
    ifstream fin("dijkstra.in");

    int x, y, c;

    fin >> n >> m;
    while (m--) {
        fin >> x >> y >> c;
        graph[x].emplace_back(y, c);
    }

    fin.close();
}

void solve() {
    memset(dist, INF, sizeof dist);
    dist[1] = 0;

    q.emplace(1, 0);

    while (!q.empty()) {
        int node = q.top().node;
        int cost = q.top().cost;
        q.pop();

        if (cost != dist[node])
            continue;

        for (const auto &son : graph[node]) {
            int new_dist = cost + son.second;
            if (new_dist < dist[son.first]) {
                dist[son.first] = new_dist;
                q.emplace(son.first, new_dist);
            }
        }
    }
}

void write() {
    ofstream fout("dijkstra.out");

    for (int i = 2; i <= n; ++i) {
        fout << (dist[i] == INF ? 0 : dist[i]) << " ";
    }

    fout.close();
}

int main() {
    read();
    solve();
    write();
    return 0;
}