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

using namespace std;

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

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

vector<pair<int, int>> G[NMAX];

int d[NMAX];

int N, M;

void dijkstra(int nodStart) {
    for (int i = 1; i <= N; i++) {
        d[i] = INF;
    }

    d[nodStart] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push({0, nodStart});

    while (!pq.empty()) {
        int distCurenta = pq.top().first;
        int nodCurent = pq.top().second;
        pq.pop();

        if (distCurenta > d[nodCurent]) {
            continue;
        }

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

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

int main() {
    fin >> N >> M;

    int x, y, c;
    for (int i = 0; i < M; i++) {
        fin >> x >> y >> c;
        G[x].push_back({y, c});
    }

    dijkstra(1);

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

    return 0;
}