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

using namespace std;
const int INF = 2000000000;

// Fisere de intrare/iesire
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

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

int D[50005];
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 costCurent = pq.top().first;
        int nodCurent = pq.top().second;
        pq.pop();
        if (costCurent > D[nodCurent]) {
            continue;
        }

        for (auto& muchie : G[nodCurent]) {
            int vecin = muchie.first;
            int costMuchie = muchie.second;
            if (D[nodCurent] + costMuchie < D[vecin]) {
                D[vecin] = D[nodCurent] + costMuchie;
                pq.push({D[vecin], vecin});
            }
        }
    }
}

int main() {
    fin >> N >> M;
    int u, v, cost;
    for (int i = 0; i < M; i++) {
        fin >> u >> v >> cost;
        G[u].push_back({v, cost});
    }

    Dijkstra(1);

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

    return 0;
}