Областная олимпиада школьников по информатике (личное первенство)

Разветвленная шпионская сеть охватывает много городов в нескольких странах. Для передачи сообщений между собой шпионы используют почту, курьеров, газетные объявления и т.д. Для каждой пары шпионских групп известно, возможно или нет передать сообщение непосредственно от одной группы другой и время, которое потребуется на передачу сообщения. Шпионская сеть построена таким образом, что всегда существует способ передать прямо или через другие группы сообщение между двумя любыми группами. Одной из шпионских групп стала известна важная информация, которую необходимо распространить как можно быстрее среди всех других групп. Напишите программу, которая вычисляет минимальное время для распространения информации во всей шпионской сети и определяет план такого распространения.

Во входном файле в первой строке содержатся два целых числа `N` и `K`, где `N` (`1\ ≤\ N\ ≤\ 100`) – количество шпионских групп, а `K` (`1\ ≤\ K\ ≤\ N`) – номер шпионской группы, которой стала известна важная информация. Далее следует `N` строк содержащих по `N` целых чисел от –1 до 100, разделенных пробелами – таблица времени передачи сообщений между группами. В `i`-ой строке `j`-ого столбца стоит время `A_{ij}` передачи сообщения от `i`-ой группы `j`-ой группе. При этом всегда `A_"ii"\ =\ 0` (`1\ ≤\ i\ ≤\ N`). Если `A_{ij}\ =\ -1`, то передать сообщение непосредственно от `i`-ой группы `j`-ой группе невозможно.

В выходной файл в первой строке вывести минимальное время распространения информации во всей шпионской сети. В следующих `(N-1)` строках нужно вывести план распространения информации за минимальное время следующим образом. Если после получения сообщения `i`-ая группа должна передать сообщение `j`-ой группе, то нужно вывести строку, содержащую два целых числа `i` и `j`, разделенных пробелом. Если существует несколько вариантов плана распространения информации за минимальное время, то можно вывести любой (один) из них.

4 1
0 -1 2 6
2 0 4 1
3 3 0 1
-1 -1 5 0

5
1 3
3 4
3 2