#include<fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#define INF 1000000000
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");
vector < pair<int,int> > L[20];
int x[20],D[20][1<<18],n,m,a,b,c,i,j,stmax,noduri,nxt,sol,vecin;
int main (){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        L[a].push_back(make_pair(b,c));
            if(b==0)
                x[a]=c;
    }
     for (i=0;i<n;i++)
        for (j=0;j<(1<<n);j++)
            D[i][j]=INF;
    stmax=(1<<n)-1;
    D[0][1]=0;
    for(noduri=1;noduri<=stmax;noduri+=2)
        for(i=0;i<n;i++)
        if(D[i][noduri]!=INF){
            for(j=0;j<L[i].size();j++){
                vecin=L[i][j].first;
                c=L[i][j].second;
                if (!(noduri&(1<<vecin))) {
                    nxt = noduri + (1<<vecin);
                    D[vecin][nxt]=min(D[vecin][nxt], D[i][noduri]+c);
                }
            }
        }

        sol=INF;
        for(i=1;i<n;i++)
        if(x[i] && D[i][stmax] != INF)
            sol=min(sol,D[i][stmax]+x[i]);

      fout<<sol;

    return 0;
}