Участники Bubble Cup X собрались после соревнования и обсуждают, как лучше всего узнать страну-организатор и города в ней.
После небольшого исследования карты Сербии участники выяснили следующий факт: в стране есть V городов, которые пронумерованы от 1 до V, и E двусторонних дорог, соединяющих города. У каждой дороги есть вес (время, необходимое для прохода по этой дороге).
На Bubble Cup есть N команд, поэтому участники придумали следующий план: каждая из N команд начнет свой путь в одном из V городов, возможно, некоторые команды будут иметь одинаковую начальную позицию.
Они хотят найти минимальное время T такое, что каждая команда может двигаться в течении этих T минут, и количество различных городов, в которых окажутся команды, как минимум K (потому что они будут исследовать только город, в котором окажутся в конце). Команда не обязана двигаться все время, если им нравится какой-то город, они могут остаться в нем и подождать, пока время пройдет.
Помогите участникам определить это минимальное время T такое, что участники закончат в минимум K различных городах, или выведите -1, если решения нет.
Обратите внимание, что между некоторыми городами может быть больше одной дороги.
Выходные данные
Выведите единственное число — минимальное время, в течение которого команды могут двигаться, чтобы закончить в хотя бы K различных городах, или выведите -1, если решения не существует.
Если решение существует, результат будет не больше 1731311.
Примечание
В примере три команды начинают из города 5, две начинают из города 2. Если они будут двигаться 3 минуты, то возможно следующее: две команды в городе 2, одна команда в городе 5, одна команда в городе 3, и одна команда в городе 1. Видно, что всего есть четыре города, в которых команды закончили путешествие.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 7 5 4
5 5 2 2 5
1 3 3
1 5 2
1 6 5
2 5 4
2 6 7
3 4 11
3 5 3
|
3
|