#include<stdio.h>
#include<assert.h>

#include<vector>
#include<algorithm>

#define a9001 1000000000
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

int verts, edges, dp[19][300000];
vector<pair<int, int> > graph[100];

void read(){
  assert(freopen("hamilton.in", "r", stdin));

  scanf("%d%d", &verts, &edges);
  for(int i = 1; i <= edges; ++i){
    int ver1, ver2, price;
    scanf("%d%d%d", &ver1, &ver2, &price);
    graph[ver1 + 1].pb(mp(ver2 + 1, price));
  }

}

void init(){
  int lim = 1 << verts;
  for(int i = 1; i <= verts; ++i)
    for(int j = 1; j < lim; ++j)
      dp[i][j] = a9001;
}

int ans = a9001;

void solve(){
  init();
  dp[1][1] = 0;

  int lim = 1 << verts;
  for(int i = 1; i < lim; ++i)
    for(int j = 1; j <= verts; ++j)
      for(int k = 0; k < graph[j].size(); ++k)
        if(i & (1 << (j - 1)))
          if(!((1 << (graph[j][k].f - 1)) & i))
            dp[graph[j][k].f][i + (1 << (graph[j][k].f - 1))] = min(dp[graph[j][k].f][i + (1 << (graph[j][k].f - 1))], dp[j][i] + graph[j][k].s);

  for(int i = 2; i <= verts; ++i)
    for(int j = 0; j < graph[i].size(); ++j)
      if(graph[i][j].f == 1)
        ans = min(ans, dp[i][lim - 1] + graph[i][j].s);

  if(ans == a9001)
    ans = -1;
}

void write(){
  assert(freopen("hamilton.out", "w", stdout));

  printf("%d", ans);
}

int main(){
  read();
  solve();
  write();
  return 0;
}