Программа, которая поможет определить между какими городами нужно достроить новые пути

В стране Грепландии построен K мост (нумерация начинается с 0). Между
некоторыми городами существуют дорожные сообщения, а возможно, нет вообще (даже
через промежуточные города). Если какое-то сочетание существует, то оно единственное.
Всего задан D дорог между какой-то парой городов (D≦ K-1). Для каждой дороги известна
цена проезда по ней.
Главному архитектору страны была поставлена задача построить еще (KD-
1) новый путь так, чтобы можно было совершать путешествия между любыми двумя
городами. Также для упрощения задания стоимость проезда по каждой новой дороге
фиксирована и равна S.
Помогите создать программу, которая поможет определить между какими городами
нужно достроить новые пути так, чтобы максимальная стоимость проезда между любыми
двумя городами была минимальной и найдите это значение.
Входные данныеПервая строка входного файла содержит целые числаK, D, S
соответственно. В следующих D строках снова записано по три целых числа A1, A2, SA (A1-A2
номера городов между которыми существует путь. SA стоимость проезда.)
1≦K≦ 100 000
0 ≦ D ≦ K-1
1 ≦ S, SA ≦ 10 000
Формат результата.Выведите единое целое число – минимально возможная
максимальная стоимость проезда между любыми двумя городами после
оптимальной достройки новых путей.
input.txt
12 8 4
0 8 8
8 2 4
2 7 8
5 11 6
5 1 14
1 3 2
1 9 10
10 6 6

output.txt
36



Объяснение для примера показано на рисунке ниже.
Зелёный цвет обозначает существующие пути между городами и стоимость проезда.
Красным цветом показаны достроенные пути с фиксированной стоимостью проезда.

0

Сообщение от megashmit В стране Грепландии построен K мост

Дальше уже читать не хочется...
Но, внимание, спойлер: дальше ни одного упоминания моста нет. Построили и забыли((

0