Problem: Mole decided to live in an abandoned mine. The structure of the mine is represented by a simple connected undirected graph which consists of N vertices numbered 1 through N and M edges. The i-th edge connects Vertices a_i and b_i, and it costs c_i yen (the currency of Japan) to remove it.

Mole would like to remove some of the edges so that there is exactly one path from Vertex 1 to Vertex N that does not visit the same vertex more than once. Find the minimum budget needed to achieve this.

Constraints

* 2 \leq N \leq 15
* N-1 \leq M \leq N(N-1)/2
* 1 \leq a_i, b_i \leq N
* 1 \leq c_i \leq 10^{6}
* There are neither multiple edges nor self-loops in the given graph.
* The given graph is connected.

Input

Input is given from Standard Input in the following format:


N M
a_1 b_1 c_1
:
a_M b_M c_M


Output

Print the answer.

Examples

Input

4 6
1 2 100
3 1 100
2 4 100
4 3 100
1 4 100
3 2 100


Output

200


Input

2 1
1 2 1


Output

0


Input

15 22
8 13 33418
14 15 55849
7 10 15207
4 6 64328
6 9 86902
15 7 46978
8 14 53526
1 2 8720
14 12 37748
8 3 61543
6 5 32425
4 11 20932
3 12 55123
8 2 45333
9 12 77796
3 9 71922
12 15 70793
2 4 25485
11 6 1436
2 7 81563
7 11 97843
3 1 40491


Output

133677

Solution (in JAVA):

Solution:
import java.util.*;
import java.util.stream.IntStream;
import java.io.*;

public class Main {

	void solve() {
		int n = in.nextInt();
		int m = in.nextInt();

		int[][] a = new int[n][n];
		for (int i = 0; i < m; i++) {
			int from = in.nextInt() - 1, to = in.nextInt() - 1, cost = in.nextInt();
			a[from][to] = a[to][from] = cost;
		}

		int[] cost = new int[1 << n];
		for (int i = 0; i < 1 << n; i++) {
			for (int x = 0; x < n; x++) {
				for (int y = x + 1; y < n; y++) {
					if ((i & (1 << x)) != 0 && (i & (1 << y)) != 0) {
						cost[i] += a[x][y];
					}
				}
			}
		}
		
		int[][] dp = new int[n][1 << n];
		int INF = Integer.MIN_VALUE / 2;
		for (int[] i : dp) {
			Arrays.fill(i, INF);
		}
		for (int mask = 0; mask < 1 << n; mask++) {
			if ((mask & 1) != 0 && (mask & (1 << (n - 1))) == 0) {
				dp[0][mask] = cost[mask];
			}
		}
		
		int[][] bits = new int[1 << n][];
		for (int i = 0; i < 1 << n; i++) {
			bits[i] = new int[Integer.bitCount(i)];
			int tmp = 0;
			for (int j = 0; j < n; j++) {
				if ((i & (1 << j)) != 0) {
					bits[i][tmp++] = j;
				}
			}
		}
		
		for (int mask = 1; mask < 1 << n; mask++) {
			for (int last = 0; last < n; last++) {
				if ((mask & (1 << last)) == 0) {
					continue;
				}
				int mx = INF;
				int andMask = mask ^ (1 << last);
				for (int submask = andMask; submask > 0; submask = (submask - 1) & andMask) {
					for (int prevLast : bits[submask]) {
						if ((submask & (1 << prevLast)) == 0) {
							continue;
						}
						if (a[last][prevLast] == 0) {
							continue;
						}
						
						int newCost = dp[prevLast][submask] + a[last][prevLast] + cost[mask ^ submask];
						if (newCost > mx) {
							mx = newCost;
						}
					}
				}
				dp[last][mask] = Math.max(dp[last][mask], mx);
			}
		}
		
		out.println(cost[(1 << n) - 1] - dp[n - 1][(1 << n) - 1]);
	}

	FastScanner in;
	PrintWriter out;

	void run() {
		in = new FastScanner();
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public FastScanner(String s) {
			try {
				br = new BufferedReader(new FileReader(s));
			} catch (FileNotFoundException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}

		public String nextToken() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
				}
			}
			return st.nextToken();
		}

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

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

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

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