#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

#define MAXN 18
#define PUT 262144
#define INF 19000000

struct node{
    int nod, cost;
};

vector <node> graf[MAXN];
int dp[MAXN][PUT];

int hasedge(int nodi, int nodf){
  int j, retval;
  retval = 0;
  for(j = 0; j < graf[nodi].size(); j++){
    if(graf[nodi][j].nod == nodf){
      retval = graf[nodi][j].cost;
    }
  }
  return retval;
}

int main()
{
    FILE *fin, *fout;
    int n, m, i, mask, j, a, b, c, put, min, retval;
    fin = fopen("hamilton.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    put = 1;
    for(i = 0; i < n; i++){
      put *= 2;
    }
    for(i = 0; i < m; i++){
        fscanf(fin, "%d%d%d", &a, &b, &c);
        graf[a].push_back({b, c});
    }
    fclose(fin);
    for(mask = 0; mask < put; mask++){
        for(i = 0; i < n; i++){
          dp[i][mask] = INF;
        }
    }
    dp[0][1] = 0;
    for(mask = 1; mask < put; mask++){
        for(i = 0; i < n; i++){
            if(((mask >> i) & 1) == 1){
                for(j = 0; j < graf[i].size(); j++){
                    if((((mask >> graf[i][j].nod) & 1) == 1) && ((dp[i][mask - (1 << graf[i][j].nod)] + graf[i][j].cost) < dp[graf[i][j].nod][mask])){
                        dp[graf[i][j].nod][mask] = dp[i][mask - (1 << graf[i][j].nod)] + graf[i][j].cost;
                    }
                }
            }
        }
    }
    min = INF;
    for(i = 1; i < n; i++){
      retval = hasedge(i, 0);
      if(retval != 0){
        if((dp[i][put - 1] + retval) < min){
          min = dp[i][put - 1] + retval;
        }
      }
    }
    fout = fopen("hamilton.out", "w");
    fprintf(fout, "%d", min);
    fclose(fout);
    return 0;
}