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 <bits/stdc++.h>
#include <cmath>

using namespace std;
typedef long long ll;
//typedef unsigned long long ll;

#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = LONG_LONG_MAX / 10;
//const ll INF = (1ll << 31) - 1;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
//const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
//typedef pair<int, int> P;
//typedef pair<double, double> P;

bool contain(set<P> &s, P a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
const int mod = 1000000007;


void print_line(vector<ll> &line) {
    if (line.size() == 0ll) {
        cout << endl;
        return;
    }
    for (ll i = 0; i < line.size(); i++) {
        cout << line[i];
        if (i == line.size() - 1) cout << endl;
        else cout << ' ';
    }
}

typedef priority_queue<long long, vector<long long>, greater<long long>> PQ_ASK;


typedef int Weight;

struct Edge {
    int src, dst;
    Weight weight;

    Edge(int src, int dst, Weight weight) :
            src(src), dst(dst), weight(weight) {}
};

bool operator<(const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
           e.src != f.src ? e.src < f.src : e.dst < f.dst;
}

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

Weight chinesePostman(const Graph &g) {
    Weight total = 0;
    vector<int> odds;
    rep(u, g.size()) {
        for (auto e: g[u]) total += e.weight;
        if (g[u].size() % 2) odds.push_back(u);
    }
    total /= 2;
    int n = odds.size(), N = 1 << n;
    Weight w[n][n]; // make odd vertices graph
    rep(u, n) {
        int s = odds[u]; // dijkstra's shortest path
        vector<Weight> dist(g.size(), INT_MAX);
        dist[s] = 0;
        vector<int> prev(g.size(), -2);
        priority_queue<Edge> Q;
        Q.push(Edge(-1, s, 0));
        while (!Q.empty()) {
            Edge e = Q.top();
            Q.pop();
            if (prev[e.dst] != -2) continue;
            prev[e.dst] = e.src;
            for (auto f:g[e.dst]) {
                if (dist[f.dst] > e.weight + f.weight) {
                    dist[f.dst] = e.weight + f.weight;
                    Q.push(Edge(f.src, f.dst, e.weight + f.weight));
                }
            }
        }
        rep(v, n) w[u][v] = dist[odds[v]];
    }
    Weight best[N]; // DP for general matching
    rep(S, N)best[S] = INT_MAX;
    best[0] = 0;

    for (int S = 0; S < N; ++S)
        for (int i = 0; i < n; ++i)
            if (!(S & (1 << i)))
                for (int j = i + 1; j < n; ++j)
                    if (!(S & (1 << j)))
                        best[S | (1 << i) | (1 << j)] = min(best[S | (1 << i) | (1 << j)], best[S] + w[i][j]);
    return total + best[N - 1];
}

int main() {
    int v, e;
    cin >> v >> e;
    Graph graph(v, Edges());

    rep(i, e) {
        int s, t, d;
        cin >> s >> t >> d;
        {
            Edge edge(s, t, d);
            graph[s].push_back(edge);
        }
        {
            Edge edge(t, s, d);
            graph[t].push_back(edge);
        }
    }
    vector<int> results;
    int ans = chinesePostman(graph);

    cout << ans << endl;

}



