#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;

const int MAXN = 15;
vector<pair<int, int> > g[MAXN + 1];
int dp[(1 << MAXN) + 1][MAXN + 1], delCost[(1 << MAXN) + 1];
vector<int> who[(1 << MAXN) + 1];

void relax(int &x, int y) {
    x = max(x, y);
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, m;
    cin >> n >> m;
    int all = 0;
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({ b, c });
        g[b].push_back({ a, c });
        all += c;
    }
    /*for(int mask = 1; mask < (1 << n); mask++) {
        for(int last = 1; last < n; last++) {
            if(dp[mask][last] == -1)
                continue;
            if(!((1 << (last - 1)) & mask))
                continue;
            for(int now = 1; now <= n; now++) {
                if((1 << (now - 1)) & mask)
                    continue;
                bool ok = false;
                int cost = 0;
                for(auto u: g[now]) {
                    if(u.first == last) {
                        ok = true;
                        cost = u.second;
                        break;
                    }
                }
                if(ok)
                    relax(dp[mask | (1 << (now - 1))][now], dp[mask][last] + cost);
            }
        }
    }*/
    for(int mask = 0; mask < (1 << n); mask++) {
        map<int, int> cur;
        for(int i = 1; i <= n; i++)
            if((1 << (i - 1)) & mask) {
                cur[i] = 1;
                who[mask].push_back(i);
            }
        int res = 0;
        for(int i = 1; i <= n; i++) {
            if(cur[i]) {
                for(auto u: g[i]) {
                    if(cur[u.first])
                        res += u.second;
                }
            }
        }
        delCost[mask] = res / 2;
    }
    for(int i = 0; i < (1 << n); i++)
        for(int j = 0; j <= n; j++)
            dp[i][j] = -1;
    for(int mask = 1; mask < (1 << n); mask++) {
        if(!(mask & 1))
            continue;
        dp[mask][1] = delCost[mask];
    }
    int ans = 0;
    for(int mask = 0; mask < (1 << n); mask++) {
        for(int submask = mask; submask; submask = (submask - 1) & mask) {
            int m1 = mask ^ submask;
            int m2 = submask;
            for(auto u: who[m1]) {
                if(dp[m1][u] == -1) continue;
                for(auto v: g[u]) {
                    if(!((1 << (v.first - 1)) & m2))
                        continue;
                    dp[mask][v.first] = max(dp[mask][v.first], dp[m1][u] + delCost[m2] + v.second);
                }
            }
        }
    }
    for(int mask = 0; mask < (1 << n); mask++)
        ans = max(ans, dp[mask][n]);
    cout << all - ans << "\n";
    return 0;
}


Measured memory_bytes: 5120