Se dă un graf conex neorientat G cu N noduri și M muchii, fiecare muchie având asociat un cost. Un arbore parțial pentru G este un subgraf cu structura de arbore, care cuprinde toate nodurile și o parte din muchii.

Cerința

Se cere găsirea unui arbore parțial al grafului G, astfel încât diferența dintre cel mai mare și cel mai mic cost al unei muchii să fie minimă.

Date de intrare

Fișierul de intrare weightdif.in conține pe prima linie numerele N și M, separate printr-un spațiu. Pe urmatoarele M linii se vor găsi muchiile grafului sub forma X Y C, cu semnificația că există muchie neorientată între X și Y de cost C.

Date de ieșire

Fișierul de ieșire weightdif.out va conține pe prima linie diferența minimă dintre cel mai mare și cel mai mic cost al muchiilor unui arbore parțial din G.

Restricții și precizări

• 2 ≤ N ≤ 30.000
• 1 ≤ M ≤ 100.000
• 1 ≤ X < Y ≤ N
• 1 ≤ C ≤ 1.000.000.000
• între oricare două noduri există cel mult o muchie.
• Pentru 20 de puncte, 1 ≤ M ≤ 20
• Pentru 20 de puncte, 2 ≤ N ≤ 100 și 1 ≤ M ≤ 100
• Pentru 20 de puncte, 2 ≤ N ≤ 1000 și 1 ≤ M ≤ 10.000
• Pentru 20 de puncte, M * (M − N) * (M − N) ≤ 10.000.000
• Pentru 20 de puncte, fără restricții adiționale

Exemplu:

weightdif.in

6 10
1 2 2
2 3 1
3 4 2
4 5 1
5 6 2
1 6 1
1 4 20
2 5 5
2 6 6
4 6 7

weightdif.out

1

Explicație

Graful din exemplu:

Un arbore parțial cu diferența minimă dintre costul maxim și cel minim de pe muchii: