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.*;
import static java.lang.Math.*;
import java.util.*;
import java.util.function.*;
import java.lang.*;

public class Main {
    final static boolean debug = false;
    final static String fileName = "";
    final static boolean useFiles = false;

    public static void main(String[] args) throws FileNotFoundException {
        long start;
        if (debug)
            start = System.nanoTime();
        InputStream inputStream;
        OutputStream outputStream;
        if (useFiles) {
            inputStream = new FileInputStream(fileName + ".in");
            outputStream = new FileOutputStream(fileName + ".out");
        } else {
            inputStream = System.in;
            outputStream = System.out;
        }
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task(in, out);
        solver.solve();
        if(debug)
            out.println((System.nanoTime() - start) / 1e+9);
        out.close();
    }
}

class Task {
    public void solve() {
        final int INFINITY = (int) 1e9;
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] dist = new int[n][n];
        int[] degree = new int[n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dist[i][j] = INFINITY;
        for (int i = 0; i < n; i++)
            dist[i][i] = 0;

        int sum = 0;
        for (int i = 0; i < m; i++) {
            int a = in.nextInt() - 1;
            int b = in.nextInt() - 1;
            int w = in.nextInt();
            sum += w;
            dist[a][b] = dist[b][a] = min(dist[a][b], w);
            degree[a]++;
            degree[b]++;
        }
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

        if (degree[0] == 0 && sum > 0){
            out.println(-1);
            return;
        }

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (degree[i] > 0 && degree[j] > 0 && dist[i][j] == INFINITY) {
                    out.println(-1);
                    return;
                }

        int[] odd = new int[n];
        int k = 0;
        for (int i = 0; i < n; i++)
            if (degree[i] % 2 == 1)
                odd[k++] = i;
        int[][] a = new int[k][k];
        for (int i = 0; i < k; i++)
            for (int j = 0; j < k; j++)
                a[i][j] = dist[odd[i]][odd[j]];
        int[] dp = new int[1 << k];
        Arrays.fill(dp, INFINITY);
        dp[0] = 0;
        for (int mask = 0; mask < (1 << k); mask++) {
            for (int i = 0; i < k; i++)
                for (int j = 0; j < k; j++) {
                    if (i != j && (mask & (1 << i)) == 0 && (mask & (1 << j)) == 0) {
                        int newMask = mask | (1 << i) | (1 << j);
                        dp[newMask] = min(dp[newMask], dp[mask] + dist[odd[i]][odd[j]]);
                    }
                }
        }
        out.println(dp[(1 << k) - 1] + sum);
    }

    private InputReader in;
    private PrintWriter out;

    Task(InputReader in, PrintWriter out) {
        this.in = in;
        this.out = out;
    }
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

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

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

    public char[] nextCharArray(){
        return next().toCharArray();
    }

    public int[] nextIntArray(int n){
        int[] result = new int[n];
        for (int i = 0; i < n; i++)
            result[i] = nextInt();
        return result;
    }

    public long[] nextLongArray(int n){
        long[] result = new long[n];
        for (int i = 0; i < n; i++)
            result[i] = nextLong();
        return result;
    }

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

    public byte nextByte(){
        return Byte.parseByte(next());
    }
}
