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>

#define DB(a) cerr << __LINE__ << ": " << #a << " = " << (a) << endl;

using namespace std;

typedef pair<int, int> pii;

#define int64 long long
#define mp make_pair
#define pb push_back

int64 oo = 1ll << 31;

int degs[20];
int64 graph [20][20];

const int maxnodes = 20;
const int maxedges = 400;

int edges, nodes;
int last[maxnodes], head[maxedges], previous[maxedges];
int flow[maxedges], cap[maxedges], cost[maxedges];
int prio[maxnodes], curflow[maxnodes], edge[maxnodes], vstate[maxnodes], q[maxnodes];

void graphClear(int _nodes) {
    fill(last, last + maxnodes, -1);
    edges = 0;
    nodes = _nodes;
}

void addEdge1(int u, int v, int _cap, int _cost) {
    head[edges] = v;
    cap[edges] = _cap;
    cost[edges] = _cost;
    flow[edges] = 0;
    previous[edges] = last[u];
    last[u] = edges++;
}

void addEdge(int u, int v, int cap, int cost) {
    addEdge1(u, v, cap, cost);
    addEdge1(v, u, 0, -cost);
}

pii maxFlowOfMinCost(int s, int t) {
    int f = 0;
    int flowCost = 0;
    while (true) {
        curflow[s] = INT_MAX;
        fill(vstate, vstate + nodes, 2);
        fill(prio, prio + nodes, INT_MAX);
        prio[s] = 0;
        int qh = 0;
        int qt = 0;
        q[qt++] = s;
        if (qt == nodes)
            qt = 0;
        while (qh != qt) {
            int u = q[qh++];
            if (qh == nodes)
                qh = 0;
            vstate[u] = 0;
            for (int e = last[u]; e >= 0; e = previous[e]) {
                int v = head[e];
                int nprio = prio[u] + cost[e];
                if (cap[e] > flow[e] && prio[v] > nprio) {
                    prio[v] = nprio;
                    edge[v] = e;
                    curflow[v] = min(curflow[u], cap[e] - flow[e]);

                    if (vstate[v] == 2) {
                        q[qt++] = v;
                        if (qt == nodes)
                            qt = 0;
                    } else if (vstate[v] == 0) {
                        if (--qh == -1)
                            qh = nodes - 1;
                        q[qh] = v;
                    }
                    vstate[v] = 1;
                }
            }
        }
        if (prio[t] == INT_MAX)
            break;
        int df = curflow[t];
        f += df;
        flowCost += df * prio[t];
        for (int v = t; v != s; v = head[edge[v] ^ 1]) {
            flow[edge[v]] += df;
            flow[edge[v] ^ 1] -= df;
        }
    }
    return make_pair(f, flowCost);
}

int main() {
	int n, m, a, b; scanf("%d %d", &n, &m);
	int64 cycle = 0;
	int64 c;

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < i; ++j)
			graph[i][j] = graph[j][i] = oo;

	for (int i = 0; i < m; ++i) {
		scanf("%d %d %lld", &a, &b, &c);
		cycle += c;
		graph[a][b] = graph[b][a] = min(graph[a][b], c);
		degs[a]++;
		degs[b]++;
	}

	for (int k = 0; k < n; ++k)
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
	            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

	vector<int> imp;
	for (int i = 0; i < n; ++i)
	    if(degs[i] % 2)
	        imp.pb(i);
	int dn = imp.size();
	int ddn = dn / 2;

	int pot = 1 << dn;
	int64 resp = oo;

	if(pot == 1)
	    resp = 0;

	vector<int> A;
	vector<int> B;
	for (int mask = 1; mask < pot; mask += 2){
		if(__builtin_popcount(mask) != ddn)
			continue;
	    A.clear();
	    B.clear();

	    for (int i = 0; i < dn; ++i)
	        if(mask & (1 << i))
	            A.pb(i);
	        else
	            B.pb(i);

	    graphClear(dn + 2);
		for (int i = 0; i < (int)A.size(); ++i)
			for (int j = 0; j < (int)B.size(); ++j){
				addEdge(A[i], B[j], 1, graph[imp[A[i]]][imp[B[j]]]);
			}
		for (int i = 0; i < (int)A.size(); ++i)
			addEdge(dn, A[i], 1, 0);
		for (int i = 0; i < (int)B.size(); ++i)
			addEdge(B[i], dn + 1, 1, 0);

		int64 flow_cost = maxFlowOfMinCost(dn, dn + 1).second;

	    if(flow_cost < resp)
	        resp = flow_cost;
	}
	printf("%lld\n", cycle + resp);

	return 0;
}

