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

using namespace std;

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

typedef pair<int, int> Edge;
typedef vector<vector<Edge>> Graph;
typedef pair<int, int> HeapNode;

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

Graph read() {
    ifstream in(IN_FILE);
    int nodes, edges;
    in >> nodes >> edges;
    auto graph = vector<vector<Edge>>(nodes);
    for (int i = 0; i < edges; i++) {
        int v, w, c;
        in >> v >> w >> c;
        graph[v - 1].push_back(Edge(w - 1, c));
    }
    in.close();
    return graph;
}

void print(const vector<int>& distances) {
    ofstream out(OUT_FILE);
    const int size = int(distances.size());
    for (int i = 1; i < size; i++) {
        out << (distances[i] == INF ? -1 : distances[i]);
        out << (i + 1 < size ? " " : "");
    }
    out << "\n";
    out.close();
}

int main() {
    const auto graph = read();
    const auto distances = dijkstra(graph, 0);
    print(distances);
    return 0;
}