Simon the Spider

Insects can reproduce at an astonishing rate. Fortunately, they also have natural predators that keep their numbers in check, and spiders are among the best known of these — which is why they appear in this problem.

Simon the Spider ate well all summer and grew heavy. The threads of his web will soon be too thin to hold his weight, so he must reinforce some of them. Producing silk is hard work, so lazy, well-fed Simon wants to spend as little material as possible. He will reinforce only some threads, but every node of the web must remain reachable using only reinforced threads.

Simon also plans to relax on one of the reinforced threads, and he wants that thread to be long. So when the total length of the reinforced threads is computed, the length of the longest reinforced thread is subtracted instead of added. In other words, the cost equals the sum of the lengths of all reinforced threads minus twice the length of the longest reinforced thread.

Help Simon choose which threads to reinforce so that this cost is as small as possible (the cost may be negative).

The input contains several webs, one after another, until end of file.

The first line of each web contains two integers $N$ and $M$: the number of nodes $N$ ($2 \le N \le 2000$) and the number of threads $M$ ($0 \le M \le 1,000,000$).

Each of the next $M$ lines describes one thread with three integers $u_i$, $v_i$, and $\ell_i$, meaning there is a thread of length $\ell_i$ between nodes $u_i$ and $v_i$ ($1 \le u_i, v_i \le N$, $u_i \ne v_i$, $1 \le \ell_i \le 100,000$). There may be more than one thread between the same pair of nodes.

For each web, print a single line with the minimum possible cost, where the cost is the sum of the lengths of all reinforced threads minus twice the length of the longest reinforced thread.

If it is impossible to reach every node from every other node through the threads, print disconnected instead.