// Dijkstra.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

int main()
{
    setlocale(0, "");
    int C[10][10];
    int n, m;
    int x, y, c;
    cout << "Введите кол-во вершин ";
    cin >> n;
    cout << endl;
    cout << "Введите кол-во ребер ";
    cin >> m;
    cout << endl;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            C[i][j] = 100;

    for (int i = 1; i <= m; i++) {
        cout << "Введите откуда ребро, куда ребро, вес ребра " << endl;
        cin >> x >> y >> c;
        C[x][y] = c;
    }

    for (int i = 1; i <= n; i++) {
        cout << endl;
        for (int j = 1; j <= n; j++) {
            cout << " " << C[i][j];
        }
    }
    cout << endl;

    // ДЕЙКСТРА
    int S[10];
    int D[10];
    // Первый цикл где обнуляется S и заполняется D для первой вершины
    for (int i = 1; i <= n; i++) {
        S[i] = 0;
        D[i] = C[1][i];
    }
    // Помечаем 1 вершину (источник) как просмотренную
    S[1] = 1; int min, w;
    // Второй цикл где n-1 проход, ищем минимальные и вносим их в S
    for (int i = 1; i <= n-1; i++) {
        // Переменная min равна 100 типа бесконечность
        min = 100;
        // Собсна поиск этого минимального ребра
        for (int j = 2; j <= n; j++) {
            // Если оно ещё не просмотрено и меньше минимума
            if ((S[j] == 0) && (D[j] < min)) {
                // То переопределяем минимум и вершину w
                min = D[j];
                w = j;
            }
        }

        // Когда наконец вышли из цикла и нашли минимальную вершину, вносим ее как просмотренную
        S[w] = 1;
        // Второй цикл, переопределяем D
        for (int j = 2; j <= n; j++) {
            // Если вершина ещё не просмотрена и новый путь больше, то переопредляем
            if ((D[j] > D[w] + C[w][j]) && (S[j] == 0)) {
                D[j] = D[w] + C[w][j];
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        cout << "k " << i << "-й вершине путь " << D[i] << endl;
    }




    return 0;
}