Untitled

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define vi vector<int>
#define bit(i, x) ((x >> i) & 1)
#define ALL(x) x.begin(), x.end()
#define REP(i, n) for (int i = 1; i <= n; ++i)
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORD(i, a, b) for (int i = a; i >= b; --i)
#define Random(lf, rt) (lf + rand() % (rt - lf + 1))
#define Task "ecycle"

using namespace std;
const int maxn = 2e5 + 7, N = 1e9 + 7, mod = 1e9 + 7;

void ADD(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
    if (x < 0) x += mod;
}
void MAXIMIZE(int &x, int y) {
    x = max(x, y);
}
void MINIMIZE(int &x, int y) {
    x = min(x, y);
}

struct Data {
    int v, w, id;
};
vector <Data> adj[16];
int edgeLen = 0, cntEdge = 0, visited[2007];

int n, m, res, Addition = N, oddDegNum;
int deg[16], kc[16][16], used[16];
vector <int> Nodes;
vector <pii> Pair;

void Dfs(int u) {
    for (Data E : adj[u]) {
        if (visited[E.id]) continue;
        visited[E.id] = 1;
        edgeLen += E.w;
        Dfs(E.v);
    }
}

void solve(int pairedNum) {
    //done pairing -> calc additional cost
    if (pairedNum == oddDegNum) {
        int curAddition = 0;
        for (pii P : Pair) 
            curAddition += kc[P.fi][P.se];
        Addition = min(Addition, curAddition);
        return;
    }

    //if not -> pair
    //find the first unused verticle to pair with another one
    int u;
    FOR(i, 0, sz(Nodes) - 1) if (!used[i]) {
        u = i; break;
    }
    used[u] = 1;
    
    //pair with another one and continue recursion
    FOR(v, 0, sz(Nodes) - 1) if (!used[v]) {
        used[v] = 1;
        Pair.pb({Nodes[u], Nodes[v]});
        solve(pairedNum + 2);
        used[v] = 0; 
        Pair.pop_back();
    }
    used[u] = 0;
    return;
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }

    //input
    cin >> n >> m;
    memset(kc, 0x3f, sizeof kc);
    REP(i, m) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].pb({v, w, ++ cntEdge});
        adj[v].pb({u, w, cntEdge});
        MINIMIZE(kc[u][v], w);
        MINIMIZE(kc[v][u], w);
        ++ deg[u];
        ++ deg[v];
        res += w;
    }

    //check if possible
    Dfs(1);
    if (edgeLen < res) {
        cout << -1;
        return 0;
    }

    //push verticles that have odd deg into a vector
    REP(i, n) if (deg[i] % 2)
        Nodes.pb(i);
    oddDegNum = sz(Nodes);

    //floyd
    REP(k, n) REP(u, n) REP(v, n)
        if (kc[u][v] > kc[u][k] + kc[k][v])
            kc[u][v] = kc[u][k] + kc[k][v];

    //recursion to pair evenDegVerticles
    solve(0);

    //print result
    cout << res + Addition;

    // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
    // cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}