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 SIZE 300005
#define MOD 1000000007LL
#define INF 1 << 29
#define LLINF 1LL << 60
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cerr<<a[i]<<((i==a.size()-1)?"\n":" ");}}
ll gcd(ll a,ll b){int c=max(a,b);int d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}
ll fact(ll a){ll b=1;FOR(i,1,a)b*=i;return b;}

struct Edge
{
  int src, dst;
  ll cost;
  Edge(int src, int dst, ll cost) :
    src(src), dst(dst), cost(cost) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<ll> Array;
typedef vector<Array> Matrix;
bool operator < (const Edge &e, const Edge &f)
{
  return e.cost != f.cost ? e.cost > f.cost : // !!INVERSE!! ???????????????????????????
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}

ll chinesePostman(const Graph &g)
{
  ll total = 0;
  vector<int> odds;
  REP(u, g.size())
  {
    for(auto e : g[u]) total += e.cost;
    if (g[u].size() % 2) odds.push_back(u);
  }
  total /= 2;
  int n = odds.size(), N = 1 << n;
  ll w[n][n]; // make odd vertices graph
  REP(u,n) {
    int s = odds[u]; // dijkstra's shortest path
    vector<ll> dist(g.size(), INF); 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.cost+f.cost)
        {
          dist[f.dst] = e.cost+f.cost;
          Q.push(Edge(f.src, f.dst, e.cost+f.cost));
        }
      }
    }
    REP(v,n) w[u][v] = dist[odds[v]];
  }
  ll best[N]; // DP for general matching
  REP(S,N) best[S] = INF;
  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 n, m; cin >> n >> m;
  Graph g(n);
  REP(i,m)
  {
    int s, t; ll c; cin >> s >> t >> c;
    g[s].push_back(Edge(s,t,c));
    g[t].push_back(Edge(t,s,c));
  }
  cout << chinesePostman(g) << endl;
  return 0;
}