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 CPP):

Solution:
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define ll long long
inline int read()
{
	int x;char c;
	while((c=getchar())<'0'||c>'9');
	for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
	return x;
}
#define MN 15
int g[MN+5][MN+5],F[1<<MN][MN+5];
ll f[1<<MN][MN+5];
vector<int> v[1<<MN];
inline void rw(ll&a,ll b){if(b>a)a=b;}
int main()
{
	int n,m,i,j,k,x,y,s=0;
	n=read();m=read();
	while(m--)x=read(),y=read(),s+=g[x][y]=g[y][x]=read();
	for(i=1;i<1<<n;++i)for(j=1;j<=n;++j)if(i&(1<<j-1))
	{
		v[i].push_back(j);
		i^=1<<j-1;
		for(x=0;x<v[i].size();++x)
		{
			F[i^(1<<j-1)][j]+=g[v[i][x]][j];
			for(y=0;y<x;++y)F[i^(1<<j-1)][j]+=g[v[i][x]][v[i][y]];
		}
		i^=1<<j-1;
	}
	memset(f,200,sizeof(f));
	for(i=1;i<1<<n;++i)if(i&1)f[i][1]=F[i][1];
	for(i=1;i<1<<n;++i)for(j=0;j<v[i].size();++j)
		for(x=i^(1<<v[i][j]-1);x&=i^(1<<v[i][j]-1);--x) 
			for(y=0;y<v[x].size();++y)if(g[v[i][j]][v[x][y]])
				rw(f[i][v[i][j]],f[x][v[x][y]]+g[v[i][j]][v[x][y]]+F[i^x][v[i][j]]);
	printf("%d",s-f[(1<<n)-1][n]);
}