#include <cstdio>   // Pentru scanf, printf
#include <vector>
#include <queue>
#include <functional> // IMPORTANT: Pentru greater

using namespace std;

const int INF = 2000000000;
const int NMAX = 50005;

// Folosim vector de perechi {vecin, cost}
vector<pair<int,int>> G[NMAX];
int d[NMAX];
int N, M;

void dijkstra(int start) {
    // Initializare
    for (int i = 1; i <= N; i++) d[i] = INF;
    d[start] = 0;

    // Min-Heap: {distanta, nod}
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        // Extragem datele (varianta clasica C++98/11 pentru compatibilitate maxima)
        int distCur = pq.top().first;
        int nod = pq.top().second;
        pq.pop();

        // Optimizarea esentiala
        if (distCur > d[nod]) continue;

        for (auto &edge : G[nod]) {
            int vecin = edge.first;
            int cost = edge.second;

            if (d[nod] + cost < d[vecin]) {
                d[vecin] = d[nod] + cost;
                pq.push({d[vecin], vecin});
            }
        }
    }
}

int main() {
    // Deschidem fisierele in modul C (mult mai rapid decat fstream)
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    // scanf este mult mai rapid decat cin/fin
    scanf("%d %d", &N, &M);

    for (int i = 0; i < M; i++) {
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        G[x].push_back({y, c});
    }

    dijkstra(1);

    for (int i = 1; i <= N; i++) {
        if (d[i] == INF)
            printf("0");
        else
            printf("%d", d[i]);
        if (i != N) printf(" ");
    }

    return 0;
}