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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;
//all pair shortest path n power 3,weight and path
public class A21D {
	static int d[][],p[][],n,m,dg[],trgt;
	static boolean v[];
	static long dp[],INF=(long)1e12;
	static ArrayList<int[]>adj[];
public static void main(String[]args) throws IOException {
	Scanner sc=new Scanner(System.in);
	PrintWriter out=new PrintWriter(System.out);
	n=sc.nextInt();
	m=sc.nextInt();
//	adj=new ArrayList[n];
	//for(int i=0;i<n;i++)adj[i]=new ArrayList<int[]>();
	d=new int[n][n];
	v=new boolean[n];
	dg=new int[n];
	for(int[]d1:d) {
		Arrays.fill(d1, Integer.MAX_VALUE);
	}
	//for(int i=0;i<n;i++)d[i][i]=0;
	int b=0;
	for(int i=0;i<m;i++) {
		int x=sc.nextInt()-1,y=sc.nextInt()-1,w=sc.nextInt();
		d[x][y]=d[y][x]=Math.min(d[x][y], w);
		dg[x]++;
		dg[y]++;
		v[x]=v[y]=true;
		b+=w;
	}
	floyd();
	boolean can=true;
	for(int i=0;i<n;i++) {
		if(v[i]&&d[0][i]==Integer.MAX_VALUE) {
			can=false;
			break;
		}
	}
	if(!can)
		out.println(-1);
	else {
		dp=new long[1<<n];
		for(int i=0;i<n;i++) {
			if(dg[i]%2==1)trgt|=1<<i;
		}
		Arrays.fill(dp, -1);
		out.println(b+dp(0));
	}
	
	out.close();
}

private static long dp(int msk) {
	if(msk==trgt)
		return 0;
	if(dp[msk]!=-1)return dp[msk];
	long min=INF;
	for(int i=0;i<n;i++)
	{
		if(!c(i,msk))continue;
		for(int j=i+1;j<n;j++) {
			if(!c(j,msk))continue;
			min=Math.min(min, dp(msk|1<<i|1<<j)+d[i][j]);
		}
	}
	return dp[msk]=min;
}

private static boolean c(int i, int msk) {
	return (msk&1<<i)==0&&(trgt&1<<i)!=0;
}

private static void floyd() {
	//algo
		for(int k=0;k<n;k++) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(d[i][k]!=Integer.MAX_VALUE&&d[k][j]!=Integer.MAX_VALUE) {
						d[i][j]=Math.min(d[i][j], d[i][k]+d[k][j]);
				}
				}	
			}
		}
}
static class Scanner 
{
	StringTokenizer st;
	BufferedReader br;

	public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

	public String next() throws IOException 
	{
		while (st == null || !st.hasMoreTokens()) 
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}
	public boolean hasNext() {return st.hasMoreTokens();}
	public int nextInt() throws IOException {return Integer.parseInt(next());}
	
	public double nextDouble() throws IOException {return Double.parseDouble(next());}
	
	public long nextLong() throws IOException {return Long.parseLong(next());}

	public String nextLine() throws IOException {return br.readLine();}
		
	public boolean ready() throws IOException {return br.ready(); }
	

}
}
