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).

The first line of the input contains two integers n and m (1 \le n \le 15,0 \le m \le 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 \le x,y \le n,1 \le w \le 10000), x,y are edge endpoints, and w is the edge length.

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