#include <iostream>
using namespace std;

int a[100][100];    // Матрица смежности
int d[100];         // Кратчайшие пути до вершин
int v[100];         // Посещенные вершины
int w, minimum;             // w - итератор вершины, minimum - минимум (гениально)

void main() {
    setlocale(LC_ALL, "Russian");

    int n;
    cout << "Введите колво вершин" << endl;
    cin >> n;

    for (int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            a[i][j] = 10000;

    cout << "Вводите смежные вершины (формат: <v1> <v2> <стоимость>, окончание ввода - 0 0 0)" << endl;
    int v1, v2, cost;
    cin >> v1 >> v2 >> cost;
    while (v1 != 0 && v2 != 0) {
        a[v1][v2] = cost;
        a[v2][v1] = cost; // Убрать, если граф ориентированый.
        cin >> v1 >> v2 >> cost;
    }

    for (int i = 2; i <= n; i++) {
        d[i] = a[1][i];
        v[i] = 0;
    }


    d[1] = 0;
    do {
        w = 1000;
        minimum = 1000;
        //Ищем ближайшую непосещенную вершину (w - вершина, minimum - расстояние до нее)
        for (int i = 2; i <= n; i++) {
            if (d[i] < minimum && v[i] == 0) {
                minimum = d[i];
                w = i;
            }
        }

        //Если такая нашлась
        if (w != 1000) {
            for (int i = 2; i <= n; i++)
                if (minimum + a[w][i] < d[i])
                    d[i] = minimum + a[w][i];

            v[w] = 1; // Помечаем вершину w посещенной
        }


    } while (w != 1000);

    for (int i = 2; i <= n; i++) {
        cout << "От 1 до " << i << ": " << d[i] << endl;
    }
}