Bandbredd

Ett datornätverk består av $N$ datorer med $M$ olika direkta länkar mellan vissa par av datorer. Varje länk $i$ har en bandbredd $b_ i$.

Bandbredden för sekvens av länkar $a_1, a_2, ... a_ k$ är minimum av bandbredden hos de individuella länkarna, dvs $min(b_{a_1}, b_{a_2}, ..., b_{a_ k})$. En sekvens av länkar med bandbredder $4, 3, 1, 2$ har således bandbredd 1.

Givet två datorer $a$ och $b$ låter vi $B(a, b)$ vara den maximala bandbredden hos alla möjliga vägar av länkar mellan $a$ och $b$. Den minimala bandbredden i hela nätverket är det minsta värdet som $B(a, b)$ antar över alla par av datorer. Så om $B(0, 1) = 1$, $B(1, 2) = 4, B(0, 2) = 3$ så är den minimala bandbredden 1.

Indata

Den första raden innehåller två heltal $1 \le N \le 100\, 000$ och $0 \le M \le 300\, 000$, antalet datorer och länkar i nätverket.

De nästa $M$ raderna innehåller tre heltal $0 \le a, b \le N - 1$ och $1 \le c \le 300\, 000$ som beskriver en direkt länk mellan datorerna $a$ och $b$ med bandbredd $c$.

Indatan är konstruerad så att det alltid finns en väg av länkar mellan vilket par av datorer som helst.

Utdata

Du ska skriva ut ett heltal $B$ - den minimala bandbredden i nätverket.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

3 3
0 1 1
1 2 2
2 0 2

2

4 3
0 1 10
1 2 9
2 3 10

9

4 5
0 1 15
1 2 10
2 3 15
3 0 10
0 2 15

15

4 6
0 1 6
0 2 7
0 3 4
1 2 2
1 3 9
2 3 3

6