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.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static final int INF = 1_000_000_009;
	static Scanner in;
	static PrintWriter out;
	
	public static void main(String[] args) {
		in = new Scanner(System.in);
		out = new PrintWriter(System.out);
		new Main().solve();
		out.close();
	}
	
	void solve() {
		int n = in.nextInt(), m = in.nextInt();
		int[][] dis = new int[n][n];
		int[] deg = new int[n];
		for (int[] arr: dis)
			Arrays.fill(arr, INF);
		int answer = 0;
		for (int i = 0; i < m; ++i) {
			int u = in.nextInt() - 1, v = in.nextInt() - 1, w = in.nextInt();
			dis[u][v] = Math.min(dis[u][v], w);
			dis[v][u] = Math.min(dis[v][u], w);
			answer += w;
			deg[u] ++;
			deg[v] ++;
		}
		for (int k = 0; k < n; ++k)
			for (int i = 0; i < n; ++i)
				for (int j = 0; j < n; ++j)
					dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
		if (m > 0) {
			for (int i = 0; i < n; ++i)
				if (!iso(i, dis)) {
					for (int j = i + 1; j < n; ++j)
						if (dis[i][j] == INF && !iso(j, dis)) {
							out.println(-1);
							return;
						}
				}
			if (iso(0, dis) && m * 2 != deg[0]) {
				out.println(-1);
				return;
			}
		}
		int[] dp = new int[(1 << n)];
		Arrays.fill(dp, INF);
		dp[0] = 0;
		for (int mask = 1; mask < (1 << n); ++mask) {
			boolean valid = (Integer.bitCount(mask) % 2 == 0);
			for (int i = 0; i < n; ++i)
				if ((mask & (1 << i)) > 0 && deg[i] % 2 == 0)
					valid = false;
			if (valid) {
				int u = getLog((mask & -mask));
				for (int i = u + 1; i < n; ++i)
					if ((mask & (1 << i)) > 0)
						dp[mask] = Math.min(dp[mask], dp[((mask ^ (1 << i)) ^ (1 << u))] + dis[u][i]);
			}
		}
		int mask = 0;
		for (int i = 0; i < n; ++i)
			if (deg[i] % 2 == 1)
				mask ^= (1 << i);
		out.println(answer + dp[mask]);
	}
	
	boolean iso(int u, int[][] dis) {
		for (int i = 0; i < dis.length; ++i)
			if (u != i && dis[i][u] != INF)
				return false;
		return true;
	}
	
	int getLog(int x) {
		int result = 0;
		while ((1 << result) < x)
			result ++;
		return result;
	}
}