#include <bits/stdc++.h>

using namespace std;
const int MAXN = 50000;
const int INF = 2e9;
struct node {
    int val, cost;
};
node top;
int dist[MAXN + 1];
vector<int> v[MAXN + 1];
vector<int> c[MAXN + 1];

bool operator <(node a, node b) {
    return a.cost > b.cost;
}

priority_queue<node> pq;

int main()
{
    FILE *fin, *fout;
    int n, m, i, x, y, nr, nod, cost, c2;
    fin = fopen("dijkstra.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for (i = 0; i < m; i++) {
        fscanf(fin, "%d%d%d", &x, &y, &cost);
        v[x].push_back(y);
        c[x].push_back(cost);
    }
    fclose(fin);
    for (i = 2; i <= n; i++) {
        dist[i] = INF;
    }

    pq.push({1, 0});
    while (!pq.empty()) {
        top = pq.top();
        pq.pop();
        nod = top.val;
        cost = top.cost;
        if (cost == dist[nod]) {
            nr = v[nod].size();
            for (i = 0; i < nr; i++) {
                x = v[nod][i];
                c2 = cost + c[nod][i];
                if (c2 < dist[x]) {
                    dist[x] = c2;
                    pq.push({x, c2});
                }
            }
        }
    }
    fout = fopen("dijkstra.out", "w");
    for (i = 2; i <= n; i++) {
        if (dist[i] == INF) {
            dist[i] = 0;
        }
        fprintf(fout, "%d ", dist[i]);
    }
    fputc('\n', fout);
    fclose(fout);
    return 0;
}