- 题目1430：Shortest Path
There is one Master In ACM_DIY called "白衣少年"(White) whose motto is "I can HOLD ANY FEMALE". Since White is really busy with HOLDING FEMALES, he has no idea of the work that is given by his boss(MALE, of course), so can you help him to solve such a simple and really easy problem:
Find a shortest path which can go through all the edges at least once in a undirected graph.
If you can solve this problem, White may give you some "tips"(You know better!)
T cases (1<=T<=5)
For each case, the first line has 2 integers n and m (1 ≤ n ≤ 20, 0 ≤ m ≤ 100000), n is the amount of vertices, and m is the amount of edges. Follow m lines contain u,v,w. (1<=u,v<=n; 1<=w<=100000).u,v are 2 endpoints of the edge while w is the length of the edge .
For each case, print one line with the length of shortest path, if the path does not exist, print -1.
2 2 3 1 1 1 1 2 1 1 2 1 3 2 1 2 3 2 3 4