Traveling Graph

0ms

65536K

Description:

You are given undirected weighted graph. Find the length of the shortest cycle which starts from the vertex 1 and passes throught all the edges at least once. Graph may contain multiply edges between a pair of vertices and loops (edges from the vertex to itself).

Input:

The first line of the input contains two integers n and m (1 ≤ n ≤ 15, 0 ≤ m ≤ 2000), n is the amount of vertices, and m is the amount of edges. Following m lines contain edges as a triples x, y, w (1 ≤ x, y ≤ n, 1 ≤ w ≤ 10000), x, y are edge endpoints, and w is the edge length.

Output:

Output minimal cycle length or -1 if it doesn't exists.

Sample Input:

Sample Output:

Sample Input:

3 2
1 2 3
2 3 4

Sample Output:

Informação

Provedor Codeforces

Código CF21D