#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <sstream>
#include <string>
#include <map>
#include <set>
#include <stdlib.h>
#include <cmath>
#include <math.h>
#include <fstream>
#include <bitset>
#include <time.h>
#include <queue>
#include <cassert>
#include <cstdio>
#include <complex>
#define int long long
using namespace std;
struct Vertex{int f; int r;};
int n, m, x, y, ci;
int matrix[15][15];
int INF = -1e13;
int answer;
    int dp[number][n];
vector<vector<int> > data, money;
vector<Vertex> snm;
int get(int vertex){
    if (snm[vertex].f == vertex) return vertex;
    snm[vertex].f = get(snm[vertex].f);
    return snm[vertex].f;
}
void unia(int first, int second){
    if (snm[first].r < snm[second].r){
        snm[first].f = second;
    }
    else if (snm[first].r > snm[second].r){
        snm[second].f = first;
    }
    else{
        snm[second].f = first;
        snm[first].r++;
    }
}
int kraskall(){
    vector<vector<int> > edges;
    for (int i=0; i < data.size(); i++){
        for (int j=0; j < data[i].size(); j++){
            vector<int> help;
            help.push_back(money[i][j]);
            help.push_back(i);
            help.push_back(data[i][j]);
            edges.push_back(help);
        }
    }
    sort(edges.begin(), edges.end(), greater<vector<int> > ());
    int ostov = 0;
    for (int i=0; i < data.size(); i++){
        Vertex v;
        v.f = i;
        v.r = 1;
        snm.push_back(v);
    }
    for (int i=0; i < edges.size(); i++){
        int first = edges[i][1];
        int second = edges[i][2];
        int p1 = get(first);
        int p2 = get(second);
        if (p1 == p2) continue;
        ostov += edges[i][0];
        unia(p1, p2);
    }
    return ostov;
}
signed main()
{
    cin >> n >> m;
    for (int i=0; i < n; i++){
        for (int j=0; j < n; j++){
            matrix[i][j] = -1;
        }
    }
    for (int i=0;i<m;i++){
        cin >> x >> y >> ci;
        matrix[x-1][y-1] = ci;
        matrix[y-1][x-1] = ci;
    }
    int number = 1 << n;
    for (int i=0; i < number; i++){
        for (int j=0;j<n;j++){
            dp[i][j] = INF;
        }
    }
    dp[1][0] = 0;
    for (int i=0; i < number; i++){
        for (int j=0; j < n; j++){
            int step = 1 << j;
            int band = step & i;
            if (band == 0) continue;
            int nm = i - step;
            for (int k=0; k < n; k++){
                if (dp[nm][k] == INF) continue;
                dp[i][j] = max(dp[i][j], dp[nm][k] + matrix[j][k]);
            }
        }
    }
    answer = 1e18;
    for (int i=0; i < number; i++){
        int tr = 0;
        int cost = dp[i][n-1];
        if (cost == INF) continue;
        int summ = 0;
        for (int j=0; j < n; j++){
            for (int k=j+1; k < n; k++){
                int st1 = 1 << j;
                int st2 = 1 << k;
                int band1 = i & st1;
                int band2 = i & st2;
                if (band1 == 0 || band2 == 0) continue;
                summ += matrix[j][k];
            }
        }
        tr += summ - cost;
        data.clear();
        int counter = 0;
        vector<int> nin;
        for (int j=0; j < n; j++){
            int nn = 1 << j;
            int band = nn & i;
            if (band != 0) counter++;
            else{
                nin.push_back(j);
            }
        }
        for (int j=0; j < n-counter+1;j++){
            vector<int> help, h1;
            money.push_back(h1);
            data.push_back(help);
        }
        for (int j=0; j < n; j++){
            for (int k=j+1;k < n; k++){
                int i1 = false;
                int i2 = false;
                int num1 = -1;
                int num2 = -1;
                for (int p=0; p < nin.size(); p++){
                    if (nin[p] == j){
                        i1 = true;
                        num1 = p;
                    }
                    if (nin[p] == k){
                        i2 = true;
                        num2 = p;
                    }
                }
                if (i1 && !i2){
                    data[0].push_back(num1 + 1);
                    data[num1+1].push_back(0);
                    money[0].push_back(matrix[j][k]);
                    money[num1+1].push_back(matrix[j][k]);
                    tr += matrix[j][k];
                }
                else if (!i1 && i2){
                    data[0].push_back(num2 + 1);
                    data[num2+1].push_back(0);
                    money[0].push_back(matrix[j][k]);
                    money[num1+1].push_back(matrix[j][k]);
                    tr += matrix[j][k];
                }
            }
        }
        tr -= kraskall();
        answer = min(answer, tr);
    }
    cout << answer << endl;
    return 0;
}