#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

vector<vector<pair<int, int>>> citireLisAdiacenta()
{
    ifstream fin("hamilton.in");
    vector<vector<pair<int,int>>> lisAdiacenta;
    int N, M;
    fin >> N >> M;
    lisAdiacenta.resize(N+1);

    for (int i = 1; i <= M; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        lisAdiacenta[x].push_back({y,c});
        lisAdiacenta[y].push_back({x,c});
    }
    return lisAdiacenta;
}


int hamilton(vector<vector<pair<int,int>>> &lisAdiacenta)
{
    vector<vector<int> > c(1 << (lisAdiacenta.size()-1), vector<int>((lisAdiacenta.size()-1), INF));   /// the matrix will have 1 << n lines and n columns
    int sol;

    c[1][0] = 0;
    for (int i = 0; i < 1 << (lisAdiacenta.size()-1); ++i) /// iterate through all cycles
		for (int j = 0; j < (lisAdiacenta.size()-1); ++j)
			if (i & (1<<j))
				for (int k = 0; k < lisAdiacenta[j].size(); ++k){
					if (i & (1<<lisAdiacenta[j][k].first))
                        c[i][j] = min(c[i][j], c[i ^ (1<<j)][lisAdiacenta[j][k].first] + lisAdiacenta[j][k].second);
				}

    sol = INF;
	for (int i = 0; i < lisAdiacenta[0].size(); ++i) {
		sol = min(sol, c[(1<<(lisAdiacenta.size()-1)) - 1][lisAdiacenta[0][i].first] + lisAdiacenta[0][i].second);
    }

    return sol;
}


int main()
{
    vector<vector<pair<int,int>>> lisAdiacenta = citireLisAdiacenta();
    int rezultat = hamilton(lisAdiacenta);
    ofstream fout("hamilton.out");
    fout << rezultat;
    return 0;
}