HFT-сервер - 2

В этой задаче на проверку необходимо сдать текстовый файл, соответствующий формату вывода. Входные данные расположены в файле "c2.txt" архива со входными данными. Скачать его можно, нажав на стрелку, расположенную в правом верхнем углу рядом с кнопкой «объявления жюри».

На долю высокочастотной торговли (high frequency trading, HFT) приходится подавляющее большинство сделок на бирже. При этом время реакции на предложение очень важно — роль играют наносекунды. Например, очень важно разместить свой сервер ближе к серверам биржи, т.к. скорость света (и, соответственно, распространения сигнала) хоть и высока, но конечна, поэтому быстрее сделку совершит тот, кто соединен с сервером биржи более коротким кабелем.

Биржи внутри страны занумерованы числами от 1 до N N и соединены между собой каналами связи, для каждой пары бирж известно, есть ли между ними прямой канал связи и, если есть, то сколько наносекунд требуется для передачи данных через него. При этом связываться с другими биржами можно через промежуточные биржи. Например, если есть канал связи между биржами A A и B B , сообщение по которому передается за X X наносекунд, а по каналу связи между биржами B B и C C сообщение передается Y Y наносекунд, то можно передать сообщение между биржами A A и C C за X + Y X + Y наносекунд. Передача через промежуточные биржи возможна, даже если существует прямой канал связи между биржами. Все каналы двусторонние, время передачи в обе стороны совпадает. Связи между странами нет.

Аренда места под сервера на бирже очень дорогая, поэтому основатели стартапа могут позволить себе разместить сервер в каждой стране только на одной бирже или в любой позиции на канале связи между парой бирж. При этом они хотят разместить сервер так, чтобы оптимальное время передачи от него до самой удаленной биржи этой страны было минимальным. Считается, что связь между сервером и биржей, на которой он размещен, осуществляется за 0 наносекунд. Помогите им найти такие биржи.

Формат ввода

В первой строке вводится число T T ( 1 T 100 1 \le T \le 100 ) — количество стран, в которых планирует работать стартап.

Далее следует T T блоков с описанием конфигурации бирж в каждой из стран.

В первой строке каждого блока содержится число N N ( 2 N 50 2 \le N \le 50 ) — количество бирж в этой стране. В следующих N N строках содержится матрица A A , описывающая каналы связи между биржами. Целое число A i , j A_{i, j} , где i i  — номер строки, а j j  — номер столбца при нумерации с единицы, задает время передачи данных между биржами в наносекундах. Если A i , j = 1 A_{i, j} = -1 , то прямого канала связи между биржами i i и j j нет.

Числа A i , j A_{i, j} не превосходят 1 0 9 10^9 .

Формат вывода

Для каждой из T T стран выведите минимальное время передачи сообщения с сервера до наиболее удаленной биржи.

Примечания

Оценка за эту задачу — 50 баллов, тестирование проводится оффлайн (баллы за задачу будут известны после окончания тура).

Во время тура проверяется, что файл содержит T T вещественных чисел.

Каждое верно найденное расстояние оценивается в 0,5 балла.