//
//  main.cpp
//  Lab1
//
//  Created by Marcin Włoczko on 03/10/2019.
//  Copyright © 2019 Marcin Włoczko. All rights reserved.
//

#include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {
    int arcs[8][3] = {
        {6, 4, 5},
        {4, 3, 3},
        {3, 1, 3},
        {6, 5, 4},
        {5, 2, 1},
        {2, 1, 1},
        {3, 2, -3},
        {5, 3, -2},
    };
    int d[6] = {0, 100, 100, 100, 100, 100};
    int pi[6] = {0, 0, 0, 0, 0, 0};

    for (int i = 1; i <= 5; i++) {
        for (int j = 0; j <= 7; j++) {
            int start = arcs[j][0] - 1;
            int end = arcs[j][1] - 1;
            int value = arcs[j][2];
            if (d[start] > value + d[end]) {
                d[start] = value + d[end];
                pi[start] = end;
            }
        }
    }

    for (int j = 0; j <= 7; j++) {
        int start = arcs[j][0] - 1;
        int end = arcs[j][1] - 1;
        int value = arcs[j][2];
        if (d[start] > value + d[end]) {
            d[start] = value + d[end];
            pi[start] = end;
        }
    }

    for (int j = 0; j <= 5; j++) {
        cout << d[j] << " ";
    }

    cout << "\n" << "pi" << "\n";
    for (int j = 0; j <= 5; j++) {
        cout << pi[j] << " ";
    }

    return 0;
}