Equilíbrio da Rede
Uma empresa possui $N$ servidores e $M$ cabos de rede disponíveis. O cabo $i$ conecta os servidores $u_i$ e $v_i$ de forma bidirecional com latência $w_i$.
Para montar a infraestrutura, a empresa deve selecionar exatamente $N-1$ cabos de forma que todos os servidores fiquem conectados entre si.
A equipe de operações exige que as latências dos cabos instalados sejam o mais uniformes possível. Por isso, define-se o desequilíbrio como:
$$\text{desequilíbrio} = w_{\max} - w_{\min}$$
onde $w_{\max}$ e $w_{\min}$ são, respectivamente, a maior e a menor latência entre os $N-1$ cabos selecionados.
Determine a seleção de $N-1$ cabos que conecta todos os servidores e possui o menor desequilíbrio possível.
Input
A primeira linha contém dois inteiros $N$ e $M$ $(2 \le N \le 1000,\ N-1 \le M \le 25000)$.
As próximas $M$ linhas contêm três inteiros $u_i$, $v_i$ e $w_i$ $(1 \le u_i, v_i \le N,\ u_i \ne v_i,\ 1 \le w_i \le 10^9)$. Podem existir múltiplos cabos entre o mesmo par de servidores.
É garantido que é possível conectar todos os servidores.
Output
Imprima um único inteiro: o menor desequilíbrio possível.
4 6 1 2 1 2 3 2 3 4 3 1 3 4 2 4 5 1 4 7
2
4 5 1 2 5 2 3 5 3 4 5 1 3 5 2 4 5
0
3 3 1 2 10 2 3 100 1 3 50
40