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.awt.geom.Point2D;
import java.text.*;
import java.math.*;
import java.util.*;

public class Main implements Runnable {

	final String filename = "";

	public void solve() throws Exception {
		int n = iread(), m = iread();
		int[][] ss = new int[n][n];
		int[][] best = new int[n][n];
		for (int i = 0; i < n; i++)
			Arrays.fill(ss[i], Integer.MAX_VALUE);
		int ans = 0;
		int start_mask = 0;
		boolean[] www = new boolean[n];
		for (int i = 0; i < m; i++) {
			int a = iread(), b = iread(), w = iread();
			a--;
			b--;
			ans += w;
			www[a] = true;
			www[b] = true;
			ss[a][b] = Math.min(ss[a][b], w);
			ss[b][a] = ss[a][b];
			start_mask ^= (1 << a);
			start_mask ^= (1 << b);
		}
		for (int i=0; i<n; i++)
			for (int j=0; j<n; j++)
				best[i][j] = ss[i][j];
		for (int i=0; i<n; i++)
			for (int j=0; j<n; j++)
				for (int k=0; k<n; k++)
				{
					if (best[j][i]==Integer.MAX_VALUE) continue;
					if (best[i][k]==Integer.MAX_VALUE) continue;
					best[j][k] = Math.min(best[j][k], best[j][i]+best[i][k]);
				}
		for (int i=1; i<n; i++)
			if (best[0][i]==Integer.MAX_VALUE && www[i])
			{
				out.write("-1\n");
				return;
			}
		int[] d = new int[1 << n];
		Arrays.fill(d, Integer.MAX_VALUE);
		d[start_mask] = 0;
		int step = 0;
		for (int i = 0; i < n; i++)
			for (int j = i + 1; j < n; j++) {
				if (ss[i][j] == Integer.MAX_VALUE)
					continue;
				for (int mask = 0; mask < 1 << n; mask++) {
					if (d[mask] == Integer.MAX_VALUE)
						continue;
					int mask2 = (mask ^ (1<<i)) ^ (1<<j);
					int w = d[mask] + ss[i][j];
					d[mask2] = Math.min(d[mask2], w);
				}
			}
		ans += d[0];
		out.write(ans+"\n");
	}
	
	void test()
	{
		int n = 15, m = n*(n-1)/2;
		System.out.println(n+" "+m);
		for (int i=0; i<n; i++)
			for (int j=i+1; j<n; j++)
				System.out.println((i+1)+" "+(j+1)+" "+1);
	}

	public void run() {
//		test();
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new BufferedWriter(new OutputStreamWriter(System.out));
			// in = new BufferedReader(new FileReader(filename+".in"));
			// out = new BufferedWriter(new FileWriter(filename+".out"));
			solve();
			out.flush();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	public int iread() throws Exception {
		return Integer.parseInt(readword());
	}

	public double dread() throws Exception {
		return Double.parseDouble(readword());
	}

	public long lread() throws Exception {
		return Long.parseLong(readword());
	}

	BufferedReader in;

	BufferedWriter out;

	public String readword() throws IOException {
		StringBuilder b = new StringBuilder();
		int c;
		c = in.read();
		while (c >= 0 && c <= ' ')
			c = in.read();
		if (c < 0)
			return "";
		while (c > ' ') {
			b.append((char) c);
			c = in.read();
		}
		return b.toString();
	}

	public static void main(String[] args) {
		try {
			Locale.setDefault(Locale.US);
		} catch (Exception e) {

		}
		new Thread(new Main()).start();
		// new Thread(null, new Main(), "1", 1<<25).start();
	}
}