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.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class D implements Runnable {
    static final long INF = 1000000000000000000L;

    int[] p;
    private int root(int x) {
        if (p[x] != x)
            return root(p[x]);
        else
            return x;
    }
    
    private void solve() throws IOException {
        int n = nextInt();
        int m = nextInt();
        long[][] g = new long[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (i == j)
                    g[i][j] = 0L;
                else
                    g[i][j] = INF;
        long ans = 0;
        int[] d = new int[n];
        p = new int[n];
        for (int i=0; i<n; ++i) p[i] = i;
        
        for (int i=0; i<m; ++i) {
            int x = nextInt() - 1;
            int y = nextInt() - 1;
            int w = nextInt();
            ans += w;
            g[x][y] = g[y][x] = Math.min(g[x][y], w);
            d[x] ++;
            d[y] ++;
            p[root(x)] = root(y);
        }
        d[0]++;
        d[0]++;
        for (int i=1; i<n; ++i)
            if (root(i) != root(0) && d[i]!=0) {
                writer.println(-1);
                return;
            }
        
        for (int k=0; k<n; ++k)
            for (int i=0; i<n; ++i)
                for (int j=i+1; j<n; ++j)
                    g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
        
        LinkedList<Integer> dd = new LinkedList<Integer>();
        for (int i=0; i<n; ++i)
            if ((d[i]&1) != 0)
                dd.add(i);
        int siz = dd.size();
        long[] dp = new long[1<<siz];
        Arrays.fill(dp, INF);
        dp[0] = 0L;
        for (int i=0; i<dp.length; ++i) if (dp[i] < INF) {
            int j;
            for (j=0; j<siz; ++j)
                if ((i&(1<<j))==0)
                    break;
            for (int k=j+1; k<siz; ++k) {
                if ((i&(1<<k))==0) {
                    int next = (i | (1<<j) | (1<<k));
                    dp[next] = Math.min(dp[next], dp[i] + g[dd.get(j)][dd.get(k)]);
                }
            }
        }
        writer.println(ans + dp[(1<<siz)-1]);
    }

    public static void main(String[] args) {
        new D().run();
    }

    BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter writer;

    public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            writer = new PrintWriter(System.out);
            solve();
            reader.close();
            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

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

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

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

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
}