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.

Examples

Input

3 3
1 2 1
2 3 1
3 1 1


Output

3


Input

3 2
1 2 3
2 3 4


Output

14
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class ProblemD {
	
	static final int INF = 1000000;
	
	public static void main(String[] args) throws IOException {
		BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);

		String[] data = s.readLine().split(" ");
		int n = Integer.valueOf(data[0]);
		int m = Integer.valueOf(data[1]);
		int[][] graph = new int[n][n];
		for (int i = 0 ; i < n ; i++) {
			Arrays.fill(graph[i], INF);
		}

		long base = 0;
		int[] deg = new int[n];
		for (int i = 0 ; i < m ; i++) {
			String[] line = s.readLine().split(" ");
			int f = Integer.valueOf(line[0]) - 1;
			int t = Integer.valueOf(line[1]) - 1;
			int w = Integer.valueOf(line[2]);
			graph[f][t] = Math.min(graph[f][t], w);
			graph[t][f] = Math.min(graph[t][f], w);
			deg[f]++;
			deg[t]++;
			base += w;
		}
		
		for (int k = 0 ; k < n ; k++) {
		     for (int i = 0 ; i < n ; i++) {
		          for (int j = 0 ; j < n ; j++) {
		        	  graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
		          }
		     }
		}

		
		
		int ptn = 0;
		for (int i = 0 ; i < n ; i++) {
			if (deg[i] % 2 == 1) {
				ptn |= 1<<i;
			}
			if (deg[i] >= 1 && graph[0][i] == INF) {
				out.println(-1);
				out.flush();
				return;
			}
		}
		
		
		long[] dp = new long[1<<n];
		Arrays.fill(dp, Long.MAX_VALUE);
		dp[ptn] = 0;
		
		for (int i = ptn ; i >= 0 ; i--) {
			if (dp[i] == Long.MAX_VALUE) {
				continue;
			}
			for (int j = 0 ; j < n ; j++) {
				if ((i & (1<<j)) >= 1) {
					for (int k = j+1 ; k < n ; k++) {
						if ((i & (1<<k)) >= 1) {
							int tptn = i - (1<<j) - (1<<k);
							dp[tptn] = Math.min(dp[tptn], dp[i] + graph[j][k]);
						}
					}
					break;
				}
			}
		}
		out.println(base + dp[0]);
		out.flush();
	}

	public static void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}
}