---

#include <iostream>
#include <vector>
#include <string>
#include <climits>

using namespace std;

struct Edge
{
    int From, To, Weight;
    Edge(int f, int t, int w) : From(f), To(t), Weight(w) {}
};

vector<int> Dijkstra(int n, const vector<Edge>& edges, int start)
{
    // Список смежности: для каждой вершины — её исходящие рёбра
    vector<vector<Edge>> graph(n);
    for (const auto& e : edges) graph[e.From].push_back(e);

    vector<int> dist(n, INT_MAX);
    dist[start] = 0;

    vector<bool> visited(n, false);

    for (int step = 0; step < n; step++)
    {
        int u = -1;
        for (int i = 0; i < n; i++)
        {
            if (!visited[i] && dist[i] != INT_MAX &&
                (u == -1 || dist[i] < dist[u]))
            {
                u = i;
            }
        }

        if (u == -1) break;
        visited[u] = true;

        for (const auto& e : graph[u])
        {
            if (dist[u] + e.Weight < dist[e.To])
            {
                dist[e.To] = dist[u] + e.Weight;
            }
        }
    }
    return dist;
}

vector<int> BellmanFord(int n, const vector<Edge>& edges, int start)
{
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;

    // Повторяем n-1 раз: пробуем улучшить все рёбра
    for (int i = 0; i < n - 1; i++)
    {
        for (const auto& e : edges)
        {
            if (dist[e.From] != INT_MAX &&
                dist[e.From] + e.Weight < dist[e.To])
            {
                dist[e.To] = dist[e.From] + e.Weight;
            }
        }
    }

    // Ещё одна проверка: если что-то улучшается — есть отриц. цикл
    for (const auto& e : edges)
    {
        if (dist[e.From] != INT_MAX &&
            dist[e.From] + e.Weight < dist[e.To])
        {
            cout << "Найден отрицательный цикл" << endl;
            break;
        }
    }

    return dist;
}

void Print(const vector<int>& dist, const vector<string>& name)
{
    for (size_t i = 0; i < dist.size(); i++)
    {
        string d = (dist[i] == INT_MAX) ? "Бесконечность" : to_string(dist[i]);
        cout << name[i] << ": " << d << endl;
    }
}

int main()
{
    vector<string> name = { "A", "B", "C", "D", "E", "F" };
    int n = 6;

    vector<Edge> edges = {
        Edge(0, 1,  4), // A B
        Edge(0, 2,  2), // A C
        Edge(1, 2,  1), // B C
        Edge(1, 3,  5), // B D
        Edge(2, 5,  3), // C F
        Edge(3, 4,  1), // D E
        Edge(4, 3, -2), // E D
        Edge(4, 5,  4), // E F
    };

    cout << "Дейкстра из A" << endl;
    Print(Dijkstra(n, edges, 0), name);

    cout << endl << "Беллмана-Форда из A" << endl;
    Print(BellmanFord(n, edges, 0), name);

    return 0;
}