가장 날씬한 신장 트리

가중치가 있는 무방향 그래프 $G$가 주어질 때, 아래에서 정의하는 신장 트리 하나를 찾아야 한다.

그래프 $G$는 순서쌍 $(V, E)$이다. 여기서 $V$는 정점의 집합 ${v_1, v_2, \dots, v_n}$이고, $E$는 무방향 간선의 집합 ${e_1, e_2, \dots, e_m}$이다. 각 간선 $e \in E$는 가중치 $w(e)$를 가진다.

신장 트리 $T$는 $n$개의 모든 정점을 $n - 1$개의 간선으로 잇는 트리(사이클이 없는 연결 부분그래프)이다. 신장 트리 $T$의 날씬함(slimness)은 $T$를 이루는 $n - 1$개 간선의 가중치 중 최댓값과 최솟값의 차로 정의한다.

그림 5: 그래프 $G$와 간선들의 가중치.

예를 들어 그림 5(a)의 그래프 $G$는 네 정점 ${v_1, v_2, v_3, v_4}$와 다섯 무방향 간선 ${e_1, e_2, e_3, e_4, e_5}$를 가진다. 그림 5(b)에서 보듯 간선의 가중치는 $w(e_1) = 3$, $w(e_2) = 5$, $w(e_3) = 6$, $w(e_4) = 6$, $w(e_5) = 7$이다.

그림 6: $G$의 신장 트리 예시.

$G$에는 여러 신장 트리가 있다. 그중 넷을 그림 6(a)~(d)에 나타냈다. 그림 6(a)의 신장 트리 $T_a$는 가중치가 $3, 6, 7$인 세 간선으로 이루어진다. 최댓값은 $7$, 최솟값은 $3$이므로 $T_a$의 날씬함은 $4$이다. 그림 6(b), (c), (d)에 나타낸 신장 트리 $T_b$, $T_c$, $T_d$의 날씬함은 각각 $3$, $2$, $1$이다. 다른 어떤 신장 트리의 날씬함도 $1$ 이상임을 쉽게 알 수 있으므로, 그림 6(d)의 신장 트리 $T_d$는 날씬함이 $1$인 가장 날씬한 신장 트리 중 하나이다.

가장 작은 날씬함을 구하는 프로그램을 작성하라.

입력은 여러 개의 데이터셋으로 이루어지며, 마지막에는 공백으로 구분된 두 개의 $0$이 있는 줄이 온다. 각 데이터셋의 형식은 다음과 같다.

n m
a1 b1 w1
...
am bm wm

데이터셋의 모든 입력 값은 음이 아닌 정수이며, 한 줄 안의 값들은 공백으로 구분된다.

$n$은 정점의 수, $m$은 간선의 수이다. $2 \le n \le 100$이고 $0 \le m \le n(n - 1)/2$라고 가정해도 된다. $a_k$와 $b_k$($k = 1, \dots, m$)는 $n$ 이하의 양의 정수로, $k$번째 간선 $e_k$가 잇는 두 정점 $v_{a_k}$와 $v_{b_k}$를 나타낸다. $w_k$는 $10000$ 이하의 양의 정수로, $e_k$의 가중치를 뜻한다. 그래프 $G = (V, E)$는 단순 그래프라고 가정한다. 즉 자기 자신을 잇는 간선(자기 루프)이나, 양 끝 정점이 서로 같은 두 개 이상의 간선(평행 간선)은 없다.

각 데이터셋에 대해, 그래프에 신장 트리가 존재하면 그중 가장 작은 날씬함을 출력한다. 존재하지 않으면 $-1$을 출력한다. 출력에 그 밖의 문자가 포함되어서는 안 된다.