Олимпа по информа

Олимпа по информа
Гарри Поттер решил организовать on-line олимпиаду среди своих друзей, однако он заметил, что в их волшебной стране всё ещё нет связи между городами и деревушками. Тогда Гарри решил силой своей волшебной палочки установить связь между населёнными пунктами волшебной страны. Посмотрев на индикатор своей чудесной палочки, он заметил, что её силы осталось слишком мало, чтобы установить прямую связь между каждой парой населенных пунктов.

Поэтому Гарри решил минимальными затратами установить связь между участниками олимпиады.

Гарри знает расстояние между всеми пунктами, которые пронумерованы от 1 до n. Населенный пункт будет включен к сети, если он будет связан с любым пунктом необязательно напрямую, то есть, возможно, через другие пункты.

Например, сеть может выглядеть так:

Известно, что затраты силы палочки на установку связи между двумя городами равно расстоянию между ними. Найдите минимальную суммарную силу волшебной палочки, необходимой для организации связи между пунктами.

Входные данные
На вход вашей программе в первой строке подаётся число n — количество населенных пунктов (1 ≤ n ≤ 1000). В последующих n*(n-1)/2 строках подаются расстояния между всеми парами пунктов волшебной страны в последовательности num1 num2 d, где num1, num2 — порядковые номера пунктов, d — расстояние между ними (1 ≤ num1, num2 ≤ n, 1 ≤ d ≤ 100). Гарантируется, что каждая пара вершин представлена во входных данных ровно один раз.

Выходные данные
Ваша программа должна вывести одно число — наименьшую суммарную силу палочки, необходимую для построения сети.

  • Могу сделать, пиши в личку