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

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(in, out);
        out.close();
    }
}

class TaskD {
    public void solve(InputReader in, PrintWriter out) {
        final int MAX = (int) 1e9;
        int n = in.nextInt();
        int m = in.nextInt();
        int sum = 0;
        int distance[][] = new int[n][n];
        int degree[] = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                distance[i][j] = MAX;
            }
        }
        for (int i = 0; i < n; i++) {
            distance[i][i] = 0;
        }
        for (int i = 0; i < m; i++) {
            int a = in.nextInt() - 1;
            int b = in.nextInt() - 1;
            int w = in.nextInt();
            sum += w;
            distance[a][b] = distance[b][a] = Math.min(distance[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++) {
                    distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[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 && distance[i][j] == MAX) {
                    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;
                k++;
            }
        }
        int dp[] = new int[1 << k];
        Arrays.fill(dp, MAX);
        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] = Math.min(dp[newMask], dp[mask] + distance[odd[i]][odd[j]]);
                    }
                }
            }
        }
        out.println(sum + dp[(1 << k) - 1]);
    }
}

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 int nextInt() {
        return Integer.parseInt(next());
    }
}