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.*;
import java.lang.*;
import java.math.*;
import java.io.*;

public class d {
	
	final int INF = Integer.MAX_VALUE / 2;
	int[][] d;
	int n, m;
	int[] deg;
	int[] best;

	private void solve() throws Exception {
		n = nextInt();
		m = nextInt();
		d = new int[n][n];
		for (int[] a : d)
			Arrays.fill(a, INF);
		for (int i = 0; i < n; ++i)
			d[i][i] = 0;
		int res = 0;
		deg = new int[n];
		for (int i = 0; i < m; ++i){
			int x, y, w;
			x = nextInt() - 1;
			y = nextInt() - 1;
			w = nextInt();
			d[x][y] = Math.min(d[x][y], w);
			d[y][x] = Math.min(d[y][x], w);
			res += w;
			++deg[x];
			++deg[y];
		}
		for (int k = 0; k < n; ++k)
			for (int x = 0; x < n; ++x)
				for (int y = 0; y < n; ++y)
					d[x][y] = Math.min(d[x][y], d[x][k] + d[k][y]);
		for (int i = 1; i < n; ++i)
			if (d[0][i] == INF && deg[i] > 0){
				out.println(-1);
				return;
			}
		int all = 0;
		int cnt = 0;
		for (int i = 0; i < n; ++i){
			if (deg[i] % 2 == 1){
				all += (1<<i);
				++cnt;
			}
		}
		if (cnt % 2 != 0)
			throw new AssertionError();
		best = new int[1<<n];
		Arrays.fill(best, -1);
		best[0] = 0;
		out.println(getBest(all) + res);
	}

	private int getBest(int mask) {
		if (best[mask] >= 0)
			return best[mask];
		best[mask] = INF;
		for (int i = 0; i < n; ++i){
			if ((mask & (1<<i)) > 0){
				for (int j = i + 1; j < n; ++j)
					if ((mask & (1<<j)) > 0){
						best[mask] = Math.min(best[mask], getBest(mask - (1<<i) - (1<<j)) + d[i][j]);
					}
				break;
			}
		}
		return best[mask];
	}

	public void run() {
		try {
			solve();
		} catch (Exception e) {
			NOO(e);
		} finally {
			out.close();
		}
	}

	PrintWriter out;
	BufferedReader in;
	StringTokenizer St;

	void NOO(Exception e) {
		e.printStackTrace();
		System.exit(1);
	}

	int nextInt() {
		return Integer.parseInt(nextToken());
	}

	long nextLong() {
		return Long.parseLong(nextToken());
	}

	double nextDouble() {
		return Double.parseDouble(nextToken());
	}

	String nextToken() {
		while (!St.hasMoreTokens()) {
			try {
				String line = in.readLine();
				St = new StringTokenizer(line);
			} catch (Exception e) {
				NOO(e);
			}
		}
		return St.nextToken();
	}

	private d(String name) {
		try {
			in = new BufferedReader(new FileReader(name + ".in"));
			St = new StringTokenizer("");
			out = new PrintWriter(new FileWriter(name + ".out"));
		} catch (Exception e) {
			NOO(e);
		}
	}

	private d() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			St = new StringTokenizer("");
			out = new PrintWriter(System.out);
		} catch (Exception e) {
			NOO(e);
		}
	}

	public static void main(String[] args) {
		Locale.setDefault(Locale.US);
		new d().run();
	}

}
