#include<fstream>
#include<vector>
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
int cost[20][20], dinamica[262148][20];
int n,m,a,b,c,mini,vecin;
vector<int>v[20];
int main(){
    in >> n >> m;
    for (int i = 0; i < n; i ++){
        for (int j = 0; j < n; j ++){
            cost[i][j] = 1e9;
        }
    }
    for (int i = 1; i <= m; i ++){
        in >> a >> b >> c;
        v[a].push_back( b );
        cost[a][b] = c;
    }
    for (int stare = 1; stare < (1 << n); stare ++){
        for (int nod = 0; nod < n; nod ++){
            dinamica[stare][nod] = 1e9;
        }
    }
    dinamica[1][0] = 0;
    for (int stare = 1; stare < (1 << n); stare ++){
        for (int nod = 0; nod < n; nod ++){
            if (dinamica[stare][nod] == 1e9){
                continue;
            }
            for (int i = 0; i < v[nod].size(); i ++){
                vecin = v[nod][i];
                if ((stare>>vecin)%2 == 1){
                    continue;
                }
                if (dinamica[ stare + (1 << vecin) ][vecin] > dinamica[stare][nod] + cost[nod][vecin]){
                    dinamica[ stare + (1 << vecin) ][vecin] = dinamica[stare][nod] + cost[nod][vecin];
                }
            }
        }
    }
    mini = 1e9;
    for (int nod = 1;nod < n; nod ++){
        if (mini > dinamica[ (1 << n) -1 ][nod] + cost[nod][0]){
            mini = dinamica[ (1 << n) -1 ][nod] + cost[nod][0];
        }
    }
    out << mini;
    return 0;
}