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

public class Main implements Runnable {
	
	final long infinity = 1000000000000000L;

	public void _main() throws IOException {
		int n = nextInt();
		int m = nextInt();
		int[] deg = new int[n];
		long[][] dist = new long[n][n];
		for (long[] arr : dist)
			Arrays.fill(arr, infinity);
		long res = 0;
		for (int i = 0; i < m; i++) {
			int a = nextInt() - 1;
			int b = nextInt() - 1;
			int c = nextInt();
			res += c;			
			++deg[a];
			++deg[b];
			dist[a][b] = dist[b][a] = Math.min(dist[a][b], c);
		}

		for (int i = 0; i < n; i++)
			dist[i][i] = 0;
		
		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]);


		for (int i = 0; i < n; i++)
			if (dist[0][i] >= infinity && deg[i] > 0) {
				out.print(-1);
				return;
		}

		/*
		deg[0] += 2;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (dist[i][j] >= infinity && deg[i] > 0 && deg[j] > 0) {
					out.print(-1);
					return;
				}
		*/


		int k = 0;
		int[] odd = new int[n];
		for (int i = 0; i < n; i++)
			if (deg[i] % 2 == 1)
				odd[k++] = i;

		long[] d = new long[1 << k];
		Arrays.fill(d, infinity);
		d[0] = 0;
		for (int mask = 0; mask < (1 << k) - 1; mask++) {
			if (d[mask] >= infinity) continue;
			int i;
			for (i = 0; i < k; i++)
				if ((mask & (1 << i)) == 0)
					break;			
			for (int j = i + 1; j < k; j++)
				if ((mask & (1 << j)) == 0) {
					int nmask = mask | (1 << i) | (1 << j);
					d[nmask] = Math.min(d[nmask], d[mask] + dist[odd[i]][odd[j]]);
				}
		}

		out.print(res + d[(1 << k) - 1]);
	}


	private BufferedReader in;
	private PrintWriter out;
	private StringTokenizer st;

	private String next() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			String rl = in.readLine();
			if (rl == null)
				return null;
			st = new StringTokenizer(rl);
		}
		return st.nextToken();
	}

	private int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	private long nextLong() throws IOException {
		return Long.parseLong(next());
	}

	private double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	public static void main(String[] args) {
		new Thread(new Main()).start();
	}

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);

			_main();

			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(202);
		}
	}

}
