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.util.regex.*;
import java.text.*;
import java.math.*;
public class Main
{
    Scanner cin;
    int [][]G;
    int N,M;
    boolean []deg;
    boolean []had;
    void work()
    {
        cin=new Scanner(System.in); 
        N=cin.nextInt();
        M=cin.nextInt();
        G=new int[N][N];
        for(int i=0;i<N;i++) Arrays.fill(G[i], Integer.MAX_VALUE/4);
        long ret=0;
        deg=new boolean[N];
        had=new boolean[N];
        for(int i=0;i<M;i++)
        {
        	int u=cin.nextInt(),v=cin.nextInt(),w=cin.nextInt();
        	ret+=w;
        	u--;v--;
        	had[u]=had[v]=true;
        	deg[u]=!deg[u];
        	deg[v]=!deg[v];
        	G[u][v]=Math.min(G[u][v], w);
        	G[v][u]=Math.min(G[v][u], w);
        }
        for(int k=0;k<N;k++)
        	for(int i=0;i<N;i++)
        		for(int j=0;j<N;j++)
        			G[i][j]=Math.min(G[i][j], G[i][k]+G[k][j]);
        for(int i=0;i<N;i++)if(G[0][i]==Integer.MAX_VALUE/4&&had[i])
        {
        	System.out.println(-1);return ;
        }
        int n=0;
        for(int i=0;i<N;i++) if(deg[i])n++;
        int []vex=new int[n];
        int top=0;for(int i=0;i<N;i++)if(deg[i]) vex[top++]=i;
        long []dp=new long[1<<n];
        Arrays.fill(dp, Long.MAX_VALUE/4);
        dp[0]=0;
        for(int i=1;i<(1<<n);i++)
        {
        	int p=0;while((i&(1<<p))==0) p++;
        	for(int j=p+1;j<n;j++)
        		if((i&(1<<j))!=0)
        		{
        			int pre=i-(1<<j)-(1<<p);
        			dp[i]=Math.min(dp[i], dp[pre]+G[vex[p]][vex[j]]);
        		}
        }
        System.out.println(ret+dp[(1<<n)-1]);
    }

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


}  

