Problem D
Simon the Spider

Simon the Spider ate many insects this summer and got fat. The threads of his web will soon be too thin to carry him and so he needs to reinforce them. Since fat spiders are also lazy, Simon wants to use as little material as possible — well, you know that spiders have to produce the material for building webs by themselves. Finally, he decided to reinforce only some of the threads, but it is important that every node of his web must be reachable over the reinforced links.

Additionally, Simon plans to spend his free time on one of the reinforced links and he wants this one link to be long. Therefore, when calculating the total length of all reinforced links, the length of the longest reinforced link will be subtracted instead of added. Help Simon to decide which links should be reinforced to have the lowest possible total length under these circumstances.

Input

The input consists of descriptions of up to $35$ webs. The first line of each description contains two numbers: the number $N$ ($2 \le N \le 1\, 000$) of nodes in the web and the number $M$ ($1 \le M \le 1\, 000\, 000$) of the links between pairs of nodes. Each of the following $M$ lines describes one link. The description of each link contains three positive integers $u_ i, v_ i, \ell _ i$, where $u_ i$ and $v_ i$ ($1 \le u_ i, v_ i \le N$ and $u_ i \neq v_ i$) are the two nodes connected by the link and $\ell _ i$ is its length ($1 \le \ell _ i \le 100\, 000$).

Output

For each web, print a single line with the minimum possible total length of reinforced links under all given conditions. Remember that the total length is the sum of the lengths of all reinforced links minus twice the length of the longest reinforced link.

If it is not possible to reach every node from every other node through a sequence of links, then print disconnected instead of the cost.

3 1
1 2 5
4 5
1 2 5
2 3 6
3 4 8
3 4 4
1 4 2

disconnected
-1