#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;
int n, m, i, j, x, y, c, d[20][20], sum, dp[1<<18], k, conf, N;
bool grad[20], bad;
vector<int> v;

int main()
{
    freopen("mmo.in", "r", stdin);
    freopen("mmo.out", "w", stdout);

    cin >> n >> m;
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            d[i][j] = (i==j ? 0 : inf);

    while(m--)
    {
        cin >> x >> y >> c;
        sum += c;
        d[x][y] = d[y][x] = c;
        grad[x] ^= 1; grad[y] ^= 1;
    }

    for(k=1; k<=n; ++k)
        for(i=1; i<=n; ++i)
            for(j=1; j<=n; ++j)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    for(i=1; i<=n; ++i)
        if(grad[i]) v.push_back(i);

    N = v.size();
    for(i=1; i<(1<<N); ++i) dp[i] = inf;

    for(conf = 0; conf < (1<<N); ++conf)
    {
        bad = 0;
        for(i=0; i<N; ++i)
            if(conf&(1<<i)) bad ^= 1;
        if(bad) continue;

        for(i=0; i<N; ++i)
            if(!(conf&(1<<i)))
                for(j=0; j<N; ++j)
                    if(i!=j && !(conf&(1<<j)))
                        dp[conf^(1<<i)^(1<<j)] = min(dp[conf^(1<<i)^(1<<j)], dp[conf] + d[v[i]][v[j]]);
    }

    cout << sum - dp[(1<<N)-1] << '\n';

    return 0;
}