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.util.*;

public class Alzhary {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		final int INFINITY = (int) 1e9;
		int n = in.nextInt();
		int m = in.nextInt();
		int[][] dist = new int[n][n];
		int[] degree = new int[n];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				dist[i][j] = INFINITY;
		for (int i = 0; i < n; i++)
			dist[i][i] = 0;

		int sum = 0;
		for (int i = 0; i < m; i++) {
			int a = in.nextInt() - 1;
			int b = in.nextInt() - 1;
			int w = in.nextInt();
			sum += w;
			dist[a][b] = dist[b][a] = Math.min(dist[a][b], w);
			degree[a]++;
			degree[b]++;
		}
		for (int k = 0; k < n; k++)
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

		if (degree[0] == 0 && sum > 0) {
			System.out.println(-1);
			return;
		}

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (degree[i] > 0 && degree[j] > 0 && dist[i][j] == INFINITY) {
					System.out.println(-1);
					return;
				}

		int[] odd = new int[n];
		int k = 0;
		for (int i = 0; i < n; i++)
			if (degree[i] % 2 == 1)
				odd[k++] = i;
		int[][] a = new int[k][k];
		for (int i = 0; i < k; i++)
			for (int j = 0; j < k; j++)
				a[i][j] = dist[odd[i]][odd[j]];
		int[] dp = new int[1 << k];
		Arrays.fill(dp, INFINITY);
		dp[0] = 0;
		int node1 = 0, node2 = 0;
		for (int mask = 0; mask < (1 << k); mask++) {
			for (int i = 0; i < k; i++)
				for (int j = 0; j < k; j++) {
					if (i != j && (mask & (1 << i)) == 0 && (mask & (1 << j)) == 0) {
						int newMask = mask | (1 << i) | (1 << j);
						dp[newMask] = Math.min(dp[newMask], dp[mask] + dist[odd[i]][odd[j]]);
						node1 = i + 1;
						node2 = j + 1;
					}
				}
		}
		// System.out.println("node1 node2 "+node1+" "+node2);
		// for(Integer i : dp){
		// System.out.print(i+" ");
		// }
		// System.out.println();
		System.out.println(dp[dp.length - 1] + sum);

	}

}