#include <bits/stdc++.h>
using namespace std;
struct Edge {
    int u, v, w;
    friend bool operator<(const Edge & a, const Edge & b) { return a.w < b.w; }
};
int main() {
    int N = 6;
    int M = 8;
    vector<Edge> edges;
    edges.push_back({4, 6, -6});
    edges.push_back({2, 3, -1});
    edges.push_back({1, 2, 1});
    edges.push_back({2, 5, 2});
    edges.push_back({2, 4, 2});
    edges.push_back({5, 3, 3});
    edges.push_back({5, 6, 4});
    sort(edges.begin(), edges.end());
    vector<int> dist(N + 1, 1e9);
    vector<int> par(N + 1, -1);
    dist[1] = 0;
    for (auto & e : edges) {
        if (dist[e.u] + e.w < dist[e.v]) {
            dist[e.v] = dist[e.u] + e.w;
            par[e.v] = e.u;
        }
    }
    cout << "Node:\t";
    for (int i = 1; i <= N; ++i) cout << i << "\t";
    cout << endl;
    cout << "Dist:\t";
    for (int i = 1; i <= N; ++i) cout << dist[i] << "\t";
    cout << endl;
    cout << "Par:\t";
    for (int i = 1; i <= N; ++i) cout << par[i] << "\t";
    cout << endl;

}