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

using namespace std;

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

const int NMAX = 50001;
#define infinit 2e9

struct State {
    int node, cost;

    bool operator < (const State & other) const {
        /// State o sa fie integrat intr-un priority queue
        /// ne propunem sa construim un min-heap de state-uri
        return cost > other.cost;
    }
};

vector < pair < int, int >> graph[NMAX];
int best_dist[NMAX];
int n, m, cost;
priority_queue < State > pq;

void read() {
    int x, y;
    fin >> n >> m;
    for (int i = 1; i <= n; i++) {
        best_dist[i] = infinit;
    }
    for (int i = 1; i <= m; ++i) {
        fin >> x >> y >> cost;
        graph[x].push_back({y, cost});
    }
}

void dijkstra(int source) {
    int node, cost;
    best_dist[source] = 0;
    pq.push({source, 0});
    while (!pq.empty()) {
        node = pq.top().node;
        cost = pq.top().cost;
        pq.pop();

        if (best_dist[node] < cost) {
            continue;
        }
        /// range-based for-loop
        /// pentru fiecare 'neighbour' din graph[node]
        /// executa ...
        for (auto edge: graph[node]) {
            int neighbour = edge.first;
            int edge_cost = edge.second;
            if (best_dist[neighbour] > cost + edge_cost) {
                best_dist[neighbour] = cost + edge_cost;
                pq.push({neighbour,best_dist[neighbour]});
            }
        }
    }
}

void print() {
    for (int i = 2; i <= n; ++i) {
        if (best_dist[i] == infinit) {
            fout << 0 << ' ';
        } else {
            fout << best_dist[i] << ' ';
        }
    }
}

int main() {
    read();
    dijkstra(1);
    print();
    return 0;
}