#include <fstream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

const string IN_FILE = "dijkstra.in";
const string OUT_FILE = "dijkstra.out";
const int INF = 0x3f3f3f3f;

struct Edge {
    int u, v, c;
};

typedef vector<vector<Edge>> Graph;

vector<int> dijkstra(const Graph& graph, const int source) {
    struct HeapNode {
        int v, c;

        bool operator<(const HeapNode& other) const {
            return c == other.c ? v < other.v : c > other.c;
        }
    };

    auto distances = vector<int>(int(graph.size()), INF);
    auto heap = priority_queue<HeapNode>();
    heap.push({source, 0});
    while (!heap.empty()) {
        const int u = heap.top().v;
        const int cost = heap.top().c;
        heap.pop();
        if (distances[u] != INF) continue;
        distances[u] = cost;
        for (const auto& e : graph[u]) {
            if (distances[e.v] == INF) {
                heap.push({e.v, cost + e.c});
            }
        }
    }
    return distances;
}

Graph readGraph() {
    ifstream in(IN_FILE);
    int V, E;
    in >> V >> E;
    auto graph = Graph(V);
    for (int i = 0; i < E; i++) {
        int u, v, c;
        in >> u >> v >> c;
        graph[u - 1].push_back({u - 1, v - 1, c});
    }
    in.close();
    return graph;
}

void writeOutput(const vector<int>& distances, const int source) {
    ofstream out(OUT_FILE);
    for (int u = 0; u < int(distances.size()); u++) {
        if (u == source) continue;
        out << (distances[u] == INF ? 0 : distances[u]);
        out << (u + 1 < int(distances.size()) ? " " : "\n");
    }
    out.close();
}

int main() {
    const int source = 0;
    const auto graph = readGraph();
    const auto distances = dijkstra(graph, source);
    writeOutput(distances, source);
    return 0;
}