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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class B {

	static final int INF = (int) 1e9;
	static boolean[] vis;
	
	static void dfs(int u, int[][] w)
	{
		vis[u] = true;
		for(int v = 0; v < vis.length; ++v)
			if(!vis[v] && w[u][v] < INF)
				dfs(v, w);
	}

	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		int base = 0, n = sc.nextInt(), m = sc.nextInt(), deg[] = new int[n];
		int[][] w = new int[n][n];
		for(int[] x: w)
			Arrays.fill(x, INF);
		
		while(m-->0)
		{
			int x = sc.nextInt() - 1, y = sc.nextInt() - 1, c = sc.nextInt();
			deg[x]++;
			deg[y]++;
			w[x][y] = w[y][x] = Math.min(w[x][y], c);
			base += c;
		}
		
		vis = new boolean[n];
		dfs(0, w);
		
		boolean good = true;
		int cntOdd = 0;
		for(int i = 0; i < n; ++i)
		{
			good &= vis[i] || deg[i] == 0;
			cntOdd += deg[i] % 2;
		}
		if(!good || cntOdd % 2 != 0)
			out.println(-1);
		else
		{
			int dist[] = new int[1 << n];
			Arrays.fill(dist, INF);
			PriorityQueue<State> pq = new PriorityQueue<>();
			int s = 0;
			for(int i = 0; i < n; ++i)
				if(deg[i] % 2 != 0)
					s |= 1 << i;
			dist[s] = 0;
			pq.add(new State(s, 0));
			while(!pq.isEmpty())
			{
				State u = pq.remove();
				if(u.cost > dist[u.st])
					continue;
				for(int x = 0; x < n; ++x)
					for(int y = x + 1; y < n; ++y)
					{
						int nst = u.st ^ 1 << x ^ 1 << y, ncost = u.cost + w[x][y];
						if(ncost < dist[nst])
							pq.add(new State(nst, dist[nst] = ncost));
					}
			}
			out.println(base + dist[0]);
		}
		out.close();
	}
	
	static class State implements Comparable<State>
	{
		int st, cost;
		
		State(int a, int b) { st = a; cost = b;}
		
		public int compareTo(State  s) { return cost - s.cost; }
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

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

		public Scanner(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

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

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

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