#include <bits/stdc++.h>
using namespace std;

/// Oriented Weighted Graph class
class OrientedGraphW {
private:
    /// Number of nodes
    size_t n_nodes;

    /// Pairs are considered as (node, weight) in this order
    vector<vector<pair<size_t, int64_t>>> graph;

public:
    OrientedGraphW(size_t n)
    :n_nodes(n){graph.resize(n_nodes);}

    size_t size() {return n_nodes;}

    void add_edge(size_t x, size_t y, int64_t weight) {
        graph[x].push_back(make_pair(y, weight));
    }

    vector<pair<size_t, int64_t>> get_edges(size_t node) {return graph[node];}
};

void read_graph(OrientedGraphW graph) {

}

/// Edge weights are being cast from long long to size_t as they must not be negative
vector<uint64_t> Dijkstra(OrientedGraphW graph, size_t start_node = 0) {
    vector<uint64_t> distances(graph.size(), numeric_limits<uint64_t>::max());

    /// Min Heap containing (weight, vertex) pairs
    priority_queue<pair<uint64_t, size_t>,
                vector<pair<uint64_t, size_t>>,
                greater<pair<uint64_t, size_t>>> heap;

    heap.push(make_pair(0, start_node));
    while(heap.size()) {
        size_t crt_node = heap.top().second;
        uint64_t crt_weight = heap.top().first;
        heap.pop();

        if(distances[crt_node] != numeric_limits<uint64_t>::max())
            continue;
        distances[crt_node] = crt_weight;

        for(pair<size_t, uint64_t> edge : graph.get_edges(crt_node))
            heap.push(make_pair(crt_weight + edge.second, edge.first));
    }

    return distances;
}

int main()
{
    ifstream f("dijkstra.in");

    int n;
    f >> n;

    OrientedGraphW graph(n);
    int x, y, w;

    f >> x;

    while(f >> x >> y >> w)
        graph.add_edge(x - 1, y - 1, w);

    f.close();

    vector<uint64_t> distances = Dijkstra(graph, 0);

    ofstream g("dijkstra.out");

    for(size_t i = 1; i < distances.size(); i++)
        if(distances[i] == numeric_limits<uint64_t>::max())
            cout << 0 << ' ';
        else
            cout << distances[i] << ' ';
    cout << "\b\n";

    g.close();

    return 0;
}