#include <vector>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <queue>

using namespace std;

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

struct Node {
    int id;
    int w; // Folosim int pentru a evita overflow la calcule
};

const int maxS = 50005;
const int INF = 1e15; // Valoare mare, dar sigura pentru adunari

int dis[maxS];
vector<Node> adj[maxS];

struct Cmp {
    bool operator()(const Node& a, const Node& b) {
        return a.w > b.w; // Min-Heap: Distanta mica are prioritate mare
    }
};

priority_queue<Node, vector<Node>, Cmp> pq;

int main() {
    int m, n;
    fin >> n >> m;

    for (int i = 1; i <= n; ++i)
        dis[i] = INF;

    dis[1] = 0;
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        adj[a].push_back({b, (int)c}); // Graf orientat
    }

    pq.push({1, 0});

    while (!pq.empty()) {
        int curr = pq.top().id;
        int d = pq.top().w;
        pq.pop();

        // DIFERENȚA CHEIE 1: Filtrarea "Stale Nodes"
        // Daca am gasit deja un drum mai scurt catre 'curr', ignoram aceasta intrare veche
        if (d > dis[curr]) continue;

        for (auto& nxt : adj[curr]) {
            // DIFERENȚA CHEIE 2: Relaxarea Conditionată (The Heart of Dijkstra)
            // Punem in coada DOAR daca drumul prin 'curr' este mai bun decat ce stiam deja
            if (dis[nxt.id] > dis[curr] + nxt.w) {
                
                // DIFERENȚA CHEIE 3: Update Imediat
                // Actualizam 'dis' ACUM, nu la iesirea din coada.
                // Asta previne inserarea de duplicate inutile in PQ.
                dis[nxt.id] = dis[curr] + nxt.w;
                pq.push({nxt.id, dis[nxt.id]});
            }
        }
    }

    for (int i = 2; i <= n; ++i) {
        if (dis[i] == INF) fout << 0 << ' ';
        else fout << dis[i] << ' ';
    }

    return 0;
}