Задан ориентированный взвешенный граф на \(n\) вершинах и \(m\) ориентированных ребрах, вес \(i\)-го ребра равен \(w_i\) (\(1 \le i \le m\)).
Нужно развернуть несколько ребер (изменить их ориентацию на противоположную) в этом графе таким образом, чтобы все вершины графа стали достижимы из какой-то одной. Стоимость таких разворотов равна максимальному весу среди всех развернутых ребер. Если можно обойтись без разворота ребер, стоимость считается равной \(0\).
Гарантируется, что в графе нет петель и кратных ребер.
Найдите наименьшую стоимость, необходимую для достижения цели. Если решения нет, выведите \(-1\).
Выходные данные
Для каждого набора входных данных выведите наименьшую необходимую стоимость. Если решения нет, выведите \(-1\).
Примечание
В первом наборе входных данных существует ребро из \(1\) в \(2\), так что все вершины уже достижимы из \(1\).
Во втором наборе входных данных невозможно добиться того, чтобы все вершины были достижимы из какой-то одной, как бы ни были развернуты ребра. Поэтому в качестве ответа нужно вывести \(-1\).
В третьем наборе входных данных можно развернуть \(4\)-е или \(5\)-е ребро. После этого все вершины станут достижимы из вершины \(1\). Для ответа выбирается \(5\)-е ребро, поскольку его вес меньше.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 1
1 2 3
5 4
1 2 10
2 3 10
3 1 10
4 5 10
4 5
1 2 10000
2 3 20000
1 3 30000
4 2 500
4 3 20
4 5
1 2 10000
2 3 20000
1 3 30000
4 2 5
4 3 20
|
0
-1
20
5
|