#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<pair<int, int> > graph[105];
int dp[20][1 << 20];
int travelling_salesman(int node, int visited) {
    if(__builtin_popcount(visited) == 1) {
        for(int i = 0; i < graph[node].size(); i++) {
            if(graph[node][i].first == 0) {
                return graph[node][i].second;
            }
        }
        return 0;
    }
    if(node == 0 and visited == 0) {
        return 0;
    }
    if(dp[node][visited] != -1) {
        return dp[node][visited];
    }
    int new_mask = visited;
    new_mask -= (1 << node);
    int result = 2e9;
    for(int i = 0; i < graph[node].size(); i++) {
        int sosed = graph[node][i].first;
        int weight = graph[node][i].second;
        if(visited & (1 << sosed)) {
            result = min(result, travelling_salesman(sosed, new_mask) + weight);
        }
    }
    
    return dp[node][visited] = result;
}
int main() {
    int n, m;
    cin >> n >> m;
    memset(dp, -1, sizeof dp);
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }
    int mask = (1 << (n)) - 1;
    cout << travelling_salesman(0, mask) << endl;
    
    return 0;
}
/*
 
 4 6
 1 2 10
 2 4 25
 2 3 35
 3 4 30
 3 1 15
 4 1 20
 
 */