For a given weighted undirected graph G(V, E), find the distance of the shortest route that meets the following criteria:

* It is a closed cycle where it ends at the same point it starts.
* The route must go through every edge at least once.

Constraints

* 2 ≤ |V| ≤ 15
* 0 ≤ |E| ≤ 1,000
* 0 ≤ di ≤ 1,000
* si ≠ ti
* The graph is connected

Input


|V| |E|
s0 t0 d0
s1 t1 d1
:
s|E|-1 t|E|-1 d|E|-1


, where |V| is the number of vertices and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target verticess of i-th edge (undirected) and di represents the distance between si and ti (the i-th edge).

Note that there can be multiple edges between a pair of vertices.

Output

Print the shortest distance in a line.

Examples

Input

4 4
0 1 1
0 2 2
1 3 3
2 3 4


Output

10


Input

4 5
0 1 1
0 2 2
1 3 3
2 3 4
1 2 5


Output

18


Input

2 3
0 1 1
0 1 2
0 1 3


Output

7
#include<bits/stdc++.h>
using namespace std;
inline int nextInt(void){
	int res=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch<='9'&&ch>='0')(res*=10)+=ch-'0',ch=getchar();
	return res;
}
short stk[20],tail=0;
inline void putInt(int x){
	if(x==0){puts("0");return;}
	while(x)stk[++tail]=x%10,x/=10;
	while(tail)putchar('0'+stk[tail--]);
	puts("");
}
const int N=15,M=1005,INF=0x3f3f3f3f;
#define bitAt(x,y) ((x>>y)&1)
#define bitFill(x) ((1<<x)-1)
#define bitChg(x,y,z) (x&(~((1<<y)|(1<<z))))
int n,m,dis[N][N],dp[1<<16],cnt[N],que[N],tot=0,ans=0;
inline int DP(int bit){
	if(~dp[bit])return dp[bit];
	if(bit==0)return dp[bit]=0;
	dp[bit]=INF;
	for(int i=0;i<tot;i++)for(int j=0;j<tot;j++)
	if(i!=j&&bitAt(bit,i)&&bitAt(bit,j))
	dp[bit]=min(dp[bit],dis[que[i]][que[j]]+DP(bitChg(bit,i,j)));
	return dp[bit];
}
signed main(void){
	memset(dp,-1,sizeof(dp));
	memset(dis,0x3f,sizeof(dis));
	n=nextInt();m=nextInt();
	for(int i=1,x,y,w;i<=m;i++){
		cnt[x=nextInt()]++,cnt[y=nextInt()]++,ans+=(w=nextInt());
		dis[x][y]=dis[y][x]=min(dis[x][y],w);
	}
	for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)
	dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	for(int i=0;i<n;i++)if(cnt[i]&1)que[tot++]=i;
	putInt(ans+DP(bitFill(tot)));
}