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

public class Main implements Runnable {
	static final int INF = Integer.MAX_VALUE / 2;

	private void solution() throws IOException {
		int n = in.nextInt();
		int m = in.nextInt();
		int[][] dist = new int[n][n];
		int[] degree = new int[n];
		for (int[] a : dist) {
			Arrays.fill(a, INF);
		}
		int res = 0;
		for (int it = 0; it < m; ++it) {
			int x = in.nextInt() - 1;
			int y = in.nextInt() - 1;
			int cost = in.nextInt();
			++degree[x];
			++degree[y];
			res += cost;
			dist[x][y] = Math.min(dist[x][y], cost);
			dist[y][x] = dist[x][y];
		}
		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]);
				}
			}
		}
		boolean ok = true;
		for (int i = 1; i < n; ++i) {
			if (degree[i] != 0 && dist[0][i] == INF) {
				ok = false;
			}
		}
		if (!ok) {
			out.println(-1);
		} else {
			int[] dp = new int[1 << n];
			Arrays.fill(dp, INF);
			dp[0] = 0;
			for (int mask = 0; mask < (1 << n); ++mask) {
				if (dp[mask] != INF) {
					for (int i = 0; i < n; ++i) {
						if (((mask >> i) & 1) == 0) {
							for (int j = i + 1; j < n; ++j) {
								if (((mask >> j) & 1) == 0) {
									int nmask = mask | (1 << i) | (1 << j);
									dp[nmask] = Math.min(dp[nmask], dp[mask] + dist[i][j]);
								}
							}
						}
					}
				}
			}
			int rmask = 0;
			for (int i = 0; i < n; ++i) {
				if (degree[i] % 2 == 1) {
					rmask |= 1 << i;
				}
			}
			out.println(res + dp[rmask]);
		}
	}

	public void run() {
		try {
			solution();
			in.reader.close();
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	private class Scanner {
		BufferedReader reader;
		StringTokenizer tokenizer;

		public Scanner(Reader reader) {
			this.reader = new BufferedReader(reader);
			this.tokenizer = new StringTokenizer("");
		}

		public boolean hasNext() throws IOException {
			while (!tokenizer.hasMoreTokens()) {
				String next = reader.readLine();
				if (next == null) {
					return false;
				}
				tokenizer = new StringTokenizer(next);
			}
			return true;
		}

		public String next() throws IOException {
			hasNext();
			return tokenizer.nextToken();
		}

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

		public String nextLine() throws IOException {
			tokenizer = new StringTokenizer("");
			return reader.readLine();
		}
	}

	public static void main(String[] args) throws IOException {
		new Thread(null, new Main(), "", 1 << 28).start();
	}
	PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	Scanner in = new Scanner(new InputStreamReader(System.in));
}
