Применим алгоритм Флойда...

В этой задаче есть ряд подводных камней.

Во-первых, в математике бесконечность обладает интереснным свойством - сколько к ней ни прибавляй (или отнимай) числа, она остается бесконечностью. Большие числа, которые мы используем в программе, этим свойством не обладают, поэтому его необходимо добавить искусственно. Просто будем считать все числа, больше либо равные половине "бесконечности", просто равными "бесконечности"

Во-вторых, если в графе много ребер отрицательного веса, то вес найденного алгоритмом Флойда цикла отрицательного веса будет очень быстро уменьшаться. Это может привести к нескольким последствиям:

• произойдет переполнение типа (при данных ограничения вес цикла может достигать -10⁴⁰ (это легко проверить экспериментально))
• вес цикла станет по абсолютной величине больше "бесконечности"

Всех этих проблем можно избежать, если использовать тип с плавающей точкой (double или extended), а в качестве бесконечности взять что-нибудь вроде 10¹⁰⁰⁰.