#include <fstream>
#include <vector>
#define NMAX 21
#define CMAX 262150
#define INF 1<<30
using namespace std;
vector <int> G[NMAX];
int n,m;
int c[CMAX][NMAX],cost[NMAX][NMAX];
inline int minim(int a, int b){
       if(a<=b) return a;
       return b;
}
int calc(int conf, int last){
    if(c[conf][last]==-1){
     c[conf][last]=INF;
     for(int i=0;i<G[last].size();i++)
      if(conf & (1<<G[last][i]))
       c[conf][last]=minim(c[conf][last], calc(conf ^ (1<<last),G[last][i]) + cost[G[last][i]][last]);
    }
    return c[conf][last];
}

int main(){
    int i,j,x,y,sol;
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");
    f>>n>>m;
    for(i=0;i<n;i++)
     for(j=0;j<n;j++) cost[i][j]=INF;
    for(i=1;i<=m;i++){
     f>>x>>y;
     G[y].push_back(x);
     f>>cost[x][y];
     }
    sol=INF;
    memset(c, -1, sizeof(c));
    c[1][0]=0;
    for(i=0;i<G[0].size();i++)
     sol=minim(sol, calc((1<<n)-1,G[0][i])+cost[G[0][i]][0]);
    g<<sol<<"\n";
    return 0;
}