거미 사이먼

곤충은 놀라운 속도로 번식한다. 다행히 곤충에게는 그 수를 억제해 주는 천적이 있으며, 거미는 그중에서도 가장 잘 알려진 포식자다. 그래서 이 문제에도 거미가 등장한다.

거미 사이먼은 여름 내내 잘 먹어서 몸이 무거워졌다. 곧 거미줄의 실이 그의 몸무게를 견디지 못할 만큼 가늘어질 것이므로, 사이먼은 일부 실을 보강해야 한다. 실을 만드는 일은 힘들기 때문에, 게으르고 배부른 사이먼은 되도록 적은 재료만 쓰고 싶어 한다. 그는 일부 실만 보강하되, 모든 마디(node)가 보강된 실만을 따라 서로 도달할 수 있어야 한다.

또한 사이먼은 보강된 실 하나에 올라가 쉬려고 하는데, 그 실이 길기를 바란다. 그래서 보강된 실들의 총 길이를 계산할 때, 가장 긴 보강된 실의 길이는 더하는 대신 뺀다. 즉, 비용은 보강된 모든 실의 길이 합에서 가장 긴 보강된 실 길이의 두 배를 뺀 값이다.

이 비용이 최소가 되도록 사이먼이 어떤 실을 보강해야 하는지 도와주자 (비용은 음수일 수도 있다).

입력은 여러 개의 거미줄로 이루어지며, 파일의 끝까지 차례로 주어진다.

각 거미줄의 첫 줄에는 두 정수 $N$과 $M$이 주어진다. $N$은 마디의 수 ($2 \le N \le 2000$), $M$은 실의 수 ($0 \le M \le 1,000,000$)이다.

이어지는 $M$개의 줄에는 각각 세 정수 $u_i$, $v_i$, $\ell_i$가 주어지며, 이는 마디 $u_i$와 $v_i$ 사이에 길이 $\ell_i$인 실이 있음을 뜻한다 ($1 \le u_i, v_i \le N$, $u_i \ne v_i$, $1 \le \ell_i \le 100,000$). 같은 두 마디 사이에 실이 여러 개 있을 수도 있다.

각 거미줄에 대해, 가능한 최소 비용을 한 줄에 출력한다. 여기서 비용은 보강된 모든 실의 길이 합에서 가장 긴 보강된 실 길이의 두 배를 뺀 값이다.

만약 실을 따라 모든 마디가 서로 도달할 수 없다면, 대신 disconnected를 출력한다.