Большинство выпускников лицея $$$31$$$ собрались поступать в московские университеты. Каждый из них выбрал максимально разные места для обучения, и некоторые пары этих мест связаны дорогами, по которым можно ходить в две стороны. У каждой дороги есть длина $$$w$$$, $$$\textbf{причём каждая дорога имеет уникальную длину}$$$. Арсению захотелось узнать, какие из данных дорог стоило бы выбрать, чтобы выполнялись следующие условия:
$$$\bullet$$$ от любого университета, из которого ведёт хотя бы одна выбранная дорога, можно добраться до любого университета, из которого ведёт хотя бы одна выбранная дорога, строго по выбранным дорогам. Более формально, все университеты $$$u$$$ такие, что существует выбранная дорога, соединяющая $$$u$$$ и какой-то город $$$v$$$, должны образовывать одну компоненту связности, если в качестве рёбер рассматривать только выбранные дороги;
$$$\bullet$$$ количество университетов в этой связной области должно быть ровно $$$k$$$.
Среди всех таких вариантов Арсений хочет найти тот, в котором наибольший общий делитель длин всех выбранных дорог был максимален, и узнать значение этого наибольшего общего делителя. Помогите ему в этом!
В первой строке находятся два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$n - 1 \leq m \leq 10^5$$$) — количество университетов и количество соединяющих их дорог соответственно.
Вторая строка содержит целое число $$$k$$$ $$$(2 \leq k \leq n)$$$, задающее размер связной области, которую должны образовать выбранные дороги.
В следующих $$$m$$$ строках заданы дороги в формате $$$u$$$, $$$v$$$, $$$w$$$ ($$$1 \leq u < v \leq n$$$, $$$2 \leq w \leq 3 \cdot 10^5$$$).
Гарантируется, что:
$$$\bullet$$$ от любого университета можно добраться до любого другого университета по дорогам, которые даны во входных данных;
$$$\bullet$$$ все $$$w_i$$$ различны, то есть для любых $$$1 \leq i < j \leq m$$$, $$$w_i \neq w_j$$$;
$$$\bullet$$$ между любой парой университетов существует не более одной дороги.
Выведите единственное число $$$x$$$ — максимальный наибольший общий делитель длин дорог среди всех вариантов выбрать дороги так, что размер компоненты связности, образованной ими, равен $$$k$$$.
5 541 2 102 3 32 4 253 4 303 5 6
5
2 121 2 300000
300000
В первом примере, ответ $$$5$$$ достигается выбором следующих дорог:
$$$(1, 2, 10)$$$, $$$(2, 4, 25)$$$, $$$(3, 4, 30)$$$.
В этой связной области $$$4$$$ места для обучения, а именно — $$$1, 2, 3, 4$$$.
Наибольший общий делитель чисел $$$(10, 25, 30) = 5$$$.
Во втором примере, есть всего один вариант — это выбрать единственную данную дорогу, поэтому ответ равен её длине.