#include <bits/stdc++.h>

using namespace std;

const int INF = 2100000000;

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

struct Data {
    int node, c;

    bool operator< (const Data &other) const {
        return c > other.c;
    }
};

int main() {

    int n, m;
    in >> n >> m; // numarul de noduri, respectiv numarul de muchii
    vector<int> dest(m + 1, 0); // dest[i] = nodul spre care orienteaza muchia i
    vector<int> last(n + 1, 0); // last[i] = prima muchia care porneste din nodul i
    vector<int> nxt(m + 1, 0); // nxt[i] = urmatoarea muchie care porneste din acelasi nod cu muchia i
    vector<int> cost(m + 1, 0); // cost[i] = costul muchiei i
    for(int i = 1; i <= m; i ++) {
        int a, b, c;
        in >> a >> b >> c;
        // adaug muchie de la a la b cu cost c
        dest[i] = b;
        nxt[i] = last[a];
        last[a] = i;
        cost[i] = c;
    }

    vector<int> dist(n + 1, INF); // vectorul de distante initializat cu INF
    dist[1] = 0; // 1 este nodul de pornire
    priority_queue<Data> q;
    q.push({1, 0});

    while(q.size() > 0) {
        Data from = q.top();
        q.pop();

        int edge = last[from.node];
        while(edge != 0) {// atat timp cat avem muchie care pleaca din nodul from
            int to = dest[edge];
            if(cost[edge] + dist[from.node] < dist[to]) {
                dist[to] = dist[from.node] + cost[edge];
                q.push({to, dist[to]});
            }

            edge = nxt[edge];
        }
    }

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


    return 0;
}