센서 네트워크

건물은 여러 개의 센서로 보호된다. 각 센서는 서로 다른 두 개의 문을 담당하며, 모든 문은 적어도 하나의 센서가 담당한다. 문을 그래프의 정점, 센서를 그래프의 간선이라고 생각하자. 이 그래프는 단순 그래프이며, 같은 두 문을 담당하는 센서는 두 개 이상 존재하지 않는다.

각 센서에는 권장 전압이 적혀 있다. 센서는 권장 전압 이상에서 동작할 수 있으며(권장 전압보다 높은 전압을 걸수록 고장 위험이 커진다), 권장 전압보다 낮은 전압에서는 절대 동작하지 않는다. 거의 모든 센서의 권장 전압은 서로 다르다.

당신은 센서의 부분집합을 켜야 한다. 어떤 부분집합이 다음 두 조건을 모두 만족하면 가능한 부분집합이라고 부른다.

• 덮개. 모든 문은 그 부분집합에 속한 센서 중 적어도 하나가 담당한다.
• 연결성. 전력은 켜져 있는 센서 하나에 공급된 뒤 전선을 통해 다른 센서로 전달된다. 전선은 같은 문을 공유하는 두 개의 켜진 센서만 연결할 수 있다(어떤 문을 두 센서가 함께 담당하면 두 센서는 이웃이다). 켜진 모든 센서에 전력이 공급되어야 하므로, 켜진 센서들은 이러한 전선을 통해 서로 도달할 수 있어야 한다. 즉 하나의 연결된 덩어리를 이루어야 한다.

켜진 모든 센서에는 같은 전압이 공급되며, 그 전압은 어떤 센서의 권장 전압보다도 낮을 수 없다. 고장 위험을 낮추기 위해, 고른 센서들의 권장 전압은 가능한 한 서로 가까워야 한다. 어떤 부분집합의 마진을 그 부분집합에 속한 센서들의 권장 전압 중 최댓값과 최솟값의 차이로 정의한다.

전체 센서 집합은 항상 가능한 부분집합이다. 가능한 모든 부분집합 중에서 마진의 최솟값을 구하라.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 하나의 빈 줄로 구분된다.

각 테스트 케이스의 첫 줄에는 문의 개수인 정수 $n$ ($2 \le n \le 350$)이 주어진다. 문은 $0$부터 $n-1$까지 번호가 매겨져 있다. 다음 줄에는 센서의 개수인 정수 $m$ ($n-1 \le m \le n(n-1)/2$)이 주어진다. 이어지는 $m$개의 줄에는 각 센서를 나타내는 세 정수 $a$, $b$, $w$ ($0 \le a \le n-1$, $0 \le b \le n-1$, $a \ne b$, $1 \le w \le 2^{15}$)가 주어진다. 이는 센서가 담당하는 서로 다른 두 문과 그 권장 전압을 뜻한다. 같은 두 문을 담당하는 센서는 존재하지 않는다.

입력의 마지막 줄에는 $0$ 하나가 주어진다.

각 테스트 케이스마다 가능한 부분집합의 최소 마진을 한 줄에 출력하라.