For a given weighted undirected graph G(V, E), find the distance of the shortest route that meets the following criteria:

* It is a closed cycle where it ends at the same point it starts.
* The route must go through every edge at least once.

Constraints

* 2 ≤ |V| ≤ 15
* 0 ≤ |E| ≤ 1,000
* 0 ≤ di ≤ 1,000
* si ≠ ti
* The graph is connected

Input


|V| |E|
s0 t0 d0
s1 t1 d1
:
s|E|-1 t|E|-1 d|E|-1


, where |V| is the number of vertices and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target verticess of i-th edge (undirected) and di represents the distance between si and ti (the i-th edge).

Note that there can be multiple edges between a pair of vertices.

Output

Print the shortest distance in a line.

Examples

Input

4 4
0 1 1
0 2 2
1 3 3
2 3 4


Output

10


Input

4 5
0 1 1
0 2 2
1 3 3
2 3 4
1 2 5


Output

18


Input

2 3
0 1 1
0 1 2
0 1 3


Output

7
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef int ll;

const int INF = 1000000000;

struct Match {
    int n;
    vector<vector<int>> a;
    vector<int> memo;

    Match(int n) : n(n) {
        a.assign(n, vector<int>(n, 0));
        memo.assign((1 << n), -1);
    }

    void add(int i, int j, int w) {
        a[i][j] = w;
        a[j][i] = w;
    }

    int solve() {
        return solve(n, 0);
    }

    int solve(int n, int s) {
        if (s == ((1 << n) - 1)) {
            return 0;
        }
        if (memo[s] != -1) {
            return memo[s];
        }
        int best = INF;
        for (int k1 = 0; k1 < n; k1++) {
            if ((s & (1 << k1)) == 0) {
                for (int k2 = k1 + 1; k2 < n; k2++) {
                    if ((s & (1 << k2)) == 0) {
                        best = min(best, a[k1][k2] + solve(n, s | (1 << k1) | (1 << k2)));
                    }
                }
            }
        }
        memo[s] = best;
        return best;
    }
};

struct FloydWarshall {
    int n;
    vector<vector<ll>> g;
    vector<vector<ll>> dists;

    FloydWarshall(int n) : n(n) {
        g.assign(n + 1, vector<ll>(n + 1, INF));
    }

    void addEdge(int from, int to, ll w) {
        g[from][to] = min(g[from][to], w);
        g[to][from] = min(g[to][from], w);
    }

    bool solve() {
        dists.assign(n + 1, vector<ll>(n + 1, INF));
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                dists[i][j] = g[i][j];
            }
            dists[i][i] = 0;
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dists[i][k] < INF && dists[k][j] < INF &&
                            dists[i][k] + dists[k][j] < dists[i][j]) {
                        dists[i][j] = dists[i][k] + dists[k][j];
                        if (i == j && dists[i][j] < 0) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
};

struct Edge {
    int from, to, w;

    Edge(int from = -1, int to = -1, int w = 0) : from(from), to(to), w(w) {
    }

    int other(int u) {
        return from == u ? to : from;
    }
};

struct Postman {
    int n;
    vector<vector<int>> g;
    vector<Edge> edges;
    int total = 0;

    Postman(int n) : n(n) {
        g.assign(n, vector<int>());
    }

    void addEdge(int u, int v, int w) {
        total += w;
        edges.push_back(Edge(u, v, w));

        g[u].push_back(edges.size() - 1);
        g[v].push_back(edges.size() - 1);
    }

    int solve() {
        vector<int> mapping;
        for (int i = 0; i < n; i++) {
            if (g[i].size() % 2 != 0) {
                mapping.push_back(i);
            }
        }
        if (mapping.size() == 0) {
            return total;
        } 
        else {
            FloydWarshall fw(n);
            for (int u = 0; u < n; u++) {
                for (int edgeId : g[u]) {
                    Edge& edge = edges[edgeId];
                    int v = edge.other(u);
                    fw.addEdge(u, v, edge.w);
                }
            }
            fw.solve();
            int nsub = mapping.size();
            Match match(nsub);
            for (int i = 0; i < nsub; i++) {
                for (int j = i + 1; j < nsub; j++) {
                    match.add(i, j, fw.dists[mapping[i]][mapping[j]]);
                }
            }
            return total + match.solve();
        }
    }

};

int main() {
    int n, e;
    cin >> n >> e;

    Postman postman(n);

    for (int i = 0; i < e; i++) {
        int from, to, w;
        cin >> from >> to >> w;
        postman.addEdge(from, to, w);
    }

    cout << postman.solve() << endl;

    return 0;
}