#include <iostream>
#include <cstdio>
#include <fstream>
using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int N = 18;
const int M = N * (N-1);
const int INF = 1e9;
const int N2 = 262144;

int cost[N][N];
int d[N2][N];

int nr;
int vf[M], urm[M], lst[N];

void adauga(int x, int y){
    vf[++nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

int main()
{
    int n,m,i,j,x,y,c,ans,p,next;
    fin >> n >> m;
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            cost[i][j] = INF;

    for(i=0; i < (1<<n); i++)
        for(j=0; j<n; j++)
            d[i][j] = INF;

    for(i=0; i<m; i++){
        fin >> x >> y >> c;
        cost[x][y] = c;
        adauga(y, x);
    }
    d[1][0] = 0;
    for(i=1; i < (1<<n); i++)
        for(j=1; j<n; j++)
            if(i & (1<<j)){
                for(p = lst[j]; p!=0; p=urm[p]){
                    next = vf[p];
                    if(i & (1<<next))
                        d[i][j] = min(d[i][j], d[i ^ (1<<j)][next] + cost[next][j]);
                }
            }
    ans = INF;
    for(j=1; j<n; j++)
        ans = min(ans, d[(1<<n) - 1][j] + cost[j][0]);
    if(ans == INF)
        fout << "-1\n";
    else
        fout << ans << "\n";
    return 0;
}