#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
#define N 20
#define Nr (1 << 18) + 5
#define For(i, a, b) for((i) = (a); (i) < (b); (i)++)
const unsigned int inf = (1 << 30) - 1;
int n, m;
vector<int> G[N];
int cst[N][N];
int c[Nr][N];
int sol;
void init();
void rezolvare();
int cost(int, int);
int main(){
init();
rezolvare();
}
void init(){
int i, j;
int x, y;
fin >> n >> m;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
cst[i][j] = inf;
For(i, 0, m){
fin >> x >> y;
fin >> cst[x][y];
G[y].push_back(x);
}
memset(c, -1, sizeof(c));
c[1][0] = 0;
}
void rezolvare(){
int i, j;
sol = inf;
For(i, 0, G[0].size())
sol = min(sol, cost((1 << n) - 1, G[0][i]) + cst[G[0][i]][0]);
fout << sol;
}
int cost(int conf, int last){
if(c[conf][last] == -1){
int i, v;
c[conf][last] = inf;
For(i, 0, G[last].size()){
v = G[last][i];
if(conf & (1 << v)){
if(v == 0 && conf != (1 << last) + 1) continue;
c[conf][last] = min(c[conf][last], cost(conf ^ (1 << last), v) + cst[v][last]);
}
}
}
return c[conf][last];
}