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
//package round21;


import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeSet;

public class D {
	private IntReader in;
	private PrintWriter out;
//	private String INPUT = "15 2000 " + add("1 2 10000 3 4 10000 ", 1000);
//	private String INPUT = "15 2000 " + add("1 2 10000 3 1 10000 ", 1000);
//	private String INPUT = "15 105 " + xx(15);
//	private String INPUT = "3 2 1 2 3 2 3 4";
//	private String INPUT = "3 3 1 2 1 2 3 1 3 1 1";
	private String INPUT = "";
	
	private String xx(int n)
	{
		StringBuilder sb = new StringBuilder();
		for(int i = 1;i <= n;i++){
			for(int j = i + 1;j <= n;j++){
				sb.append(i + " " + j + " 1 ");
			}
		}
		return sb.toString();
	}
	
	public void solve()
	{
		int n = in.nui();
		int m = in.nui();
		int[][] d = new int[n][n];
		for(int i = 0;i < n;i++){
			Arrays.fill(d[i], -1);
		}
		
		long len = 0L;
		int[] v = new int[n];
		for(int i = 0;i < m;i++){
			int x = in.nui() - 1;
			int y = in.nui() - 1;
			int w = in.nui();
			if(d[x][y] == -1 || w < d[x][y]){
				d[x][y] = w;
				d[y][x] = w;
			}
			v[x]++;
			v[y]++;
			len += w;
		}
		
		int con = 1;
		for(int i = 0;i < 15;i++){
			for(int j = 0;j < n;j++){
				if(((con >> j) & 1) == 1){
					for(int k = 0;k < n;k++){
						if(d[j][k] >= 0){
							con |= 1 << k;
						}
					}
				}
			}
		}
		for(int i = 0;i < n;i++){
			if(((con >> i) & 1) == 0){
				for(int j = 0;j < n;j++){
					if(d[i][j] >= 0){
						out.println(-1);
						return;
					}
				}
			}
		}
		
		boolean[] used = new boolean[n];
		for(int i = 0;i < n;i++){
			used[i] = v[i] % 2 == 0;
		}
		
		int[][] dddd = new int[n][n];
		for(int r = 0;r < n;r++){
			final int[] td = new int[n];
			Arrays.fill(td, -1);
			TreeSet<Integer> ts = new TreeSet<Integer>(new Comparator<Integer>(){
				@Override
				public int compare(Integer a, Integer b) {
					if(td[a] != td[b])return td[a] - td[b];
					return a - b;
				}
			});
			ts.add(r);
			td[r] = 0;
			
			while(ts.size() > 0){
				int cur = ts.pollFirst();
				
				for(int i = 0;i < d.length;i++){
					if(d[cur][i] > 0){
						int nd = td[cur] + d[cur][i];
	//					tr(cur, i, td[cur], d[cur][i], nd);
						if(td[i] == -1 || nd < td[i]){
							td[i] = nd;
							ts.add(i);
						}
					}
				}
			}
			
			for(int i = 0;i < td.length;i++){
				dddd[r][i] = td[i];
			}
		}
		
		long r = rec(used, dddd, 0);
		if(r == -1){
			out.println(-1);
		}else{
			out.println(len + r);
		}
	}
	
	private long rec(boolean[] used, int[][] d, int pos)
	{
		if(pos == used.length)return 0;
		if(!used[pos]){
			used[pos] = true;
			long min = Long.MAX_VALUE;
			for(int i = pos + 1;i < used.length;i++){
				if(!used[i]){
					int dd = d[pos][i];
					if(dd >= 0){
						used[i] = true;
						long ddd = rec(used, d, pos + 1);
						if(ddd >= 0){
							if(dd + ddd < min){
								min = dd + ddd;
							}
						}
						used[i] = false;
					}
				}
			}
			used[pos] = false;
			return min == Long.MAX_VALUE ? -1 : min;
		}else{
			return rec(used, d, pos + 1);
		}
	}
	
	public void run() throws Exception
	{
		in = INPUT.isEmpty() ? new IntReader(System.in) : new IntReader(new ByteArrayInputStream(INPUT.getBytes()));
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
	}
	
	
	public static void main(String[] args) throws Exception
	{
		new D().run();
	}
	
	public class IntReader {
		private InputStream is;
		
		public IntReader(InputStream is)
		{
			this.is = is;
		}
		
		public int nui()
		{
			try {
				int num = 0;
				while((num = is.read()) != -1 && (num < '0' || num > '9'));
				num -= '0';
				
				while(true){
					int b = is.read();
					if(b == -1)return num;
					if(b >= '0' && b <= '9'){
						num = num * 10 + (b - '0');
					}else{
						return num;
					}
				}
			} catch (IOException e) {
			}
			return -1;
		}
	}
	private static void tr(Object... o) { System.out.println(o.length == 1 ? o[0] : Arrays.toString(o)); }
	
	public static String add(String str, int k)
	{
		StringBuilder mul = new StringBuilder(str);
		StringBuilder ret = new StringBuilder();
		for(int i = k;i > 0;i >>= 1){
			if((i & 1) == 1)ret.append(mul);
			mul.append(mul);
		}
		return ret.toString();
	}
}
