A traveller, Yuan-Ling is visiting Tainan City. This city is located Southern TAIWAN, famous for traditionally old cities. There are several historic sites in Tainan city, some of which are connected by shopping streets. For convenience, we can view the historic sites and streets as a graph such that historic sites are represented by nodes and streets are represented by edges. The edges have nonnegative weights representing distance or time. Yuan-Ling would like to traverse all the streets, starting and ending at historic site ``Tainan Main Station". Your task is to help Yuan-Ling seek a closed walk that minimizes the total weight (the sum of the edges' weights in the walk) such that all the streets are traversed at least once. We call such a walk as a minimum closed walk. A walk is a list v0, e1, v1,..., ek, vk of nodes and edges such that, for 1<=i<=k , the edge ei has endpoints vi-1 and vi . Note that a walk may repeat nodes and edges. A walk is closed if its end-nodes are the same.
Given a graph G = (V, E) , we use 1, 2,...,| V| to represent the nodes. Each edge (u, v) is associated with the weight w(u, v) that is a positive integer. Your task is to write a computer program to compute the weight of a minimum closed walk that traverses all the edges at least once.
Technical Specification
The first line of the input file contains an integer indicating the number of test cases to follow. The input consists of a number of test cases. Each test case consists of a graph G = (V, E) , which has the following format: the first line contains two numbers, n(= | V|) and m(= | E|) , separated by a single space. The next m lines contain the description of m edges and the corresponding weights such that one line contains two end-nodes of an edge and the corresponding weight. Each line is represented by three positive numbers separated by a single space; the first number representing one end-node, the second representing the other end-node, and the third representing its weight. Finally, a 0 at the (m + 2) th line indicates the end of this test case.
The next test case starts after the previous ending symbol `0'. A `-1' signals the end of the whole inputs.
The output contains one line for each test case. Each line contains an integer, which is the weight of a minimum closed walk that traverses all the edges at least once.