#include <iostream>
#include <fstream>
#include <windows.h>
#include <list>

#define inf 100000

using namespace std;

struct Edges {
    int a, b, w;
};

struct Graph {
    Edges* edge;
    int* dist;
    list<int>* way; //пути
    int numVer; //число вершин
    int index;
};

void create(int m, Graph& G);
void addEdge(int top1, int top2, int weight, Graph& G);
void BellmanFord(int s, Graph& G);
void Print(int s, Graph& G);
void clear(Graph& G);


int main() {
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);

    ifstream FileIn("in.txt", ios_base::in);
    int read, ver, c = 0, weight, num;
    FileIn >> c;
    Graph G;
    create(c, G);
    do {
        cout << "Введите номер вершины, расстояния от кроторой необходимо найти(0 - " << c - 1 << "): ";
        cin >> num;
    } while ((num < 0) || (num > (c - 1)));
    c = 0;
    while (!FileIn.eof()) {
        if (c == 0) {
            c = 1;
            FileIn >> ver;
        }
        else if (FileIn.get() == '\n') {
            c = 0;
        }
        else {
            FileIn >> read;
            FileIn >> weight;
            addEdge(ver, read, weight, G);
        }
    }
    BellmanFord(num, G);
    Print(num, G);
    clear(G);
    system("Pause");
    return 0;
}



void create(int m, Graph& G) {
    G.edge = new Edges[m * (m - 1)];
    G.numVer = m;
    G.way = new list<int>[m];
    G.dist = new int[m];
    G.index = 0;
}

void addEdge(int a, int b, int weight, Graph& G) {
    G.edge[G.index].a = a;
    G.edge[G.index].b = b;
    G.edge[G.index].w = weight;
    G.index++;
}

void BellmanFord(int s, Graph& G) {
    int i, j;
    for (i = 0; i < G.numVer; i++)
        G.dist[i] = inf;
    G.dist[s] = 0;
    for (i = 0; i < G.numVer; ++i) {
        for (j = 0; j < G.index; j++) {
            if (G.dist[G.edge[j].a] + G.edge[j].w < G.dist[G.edge[j].b]) {
                G.dist[G.edge[j].b] = G.dist[G.edge[j].a] + G.edge[j].w;
                G.way[G.edge[j].b] = G.way[G.edge[j].a];
                G.way[G.edge[j].b].push_front(G.edge[j].a);
                G.way[G.edge[j].b].push_front(G.edge[j].b);
            }
        }
    }
}

void Print(int s, Graph& G) {
    for (int i = 0; i < G.numVer; i++) {
        cout << s;
        while (!G.way[i].empty()) {
            if (G.way[i].back() == s);
                G.way[i].pop_back();
            if (G.way[i].back() == i) {
                G.way[i].pop_back();
                if (G.way[i].empty())
                    G.way[i].push_front(i);
            }
            cout << "->" << G.way[i].back();
            G.way[i].pop_back();
        }
        cout << "\tРасстояние: " << G.dist[i] << endl;
    }
}

void clear(Graph& G) {
    delete[] G.edge;
    delete[] G.dist;
    delete[] G.way;
}