#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n, m, x, y, c, cod, minim, val, codnou, bit, i, j;
int d[(1<<18)][18], a[20][20];

/// d [ noduri folosite ][ nod curent ]

int main(){
    fin>>n>>m;
    for(i=1; i<=m; i++){
        fin>>x>>y>>c;
        a[x][y]=c;
    }
    int stop=(1<<n)-1;
    for(i=0; i<=stop; i++){
        for(j=0; j<n; j++){
            d[i][j]=1000000000;
        }
    }
    minim=1000000000;
    d[1][0]=0;
    for(cod=1; cod<=stop; cod++){
        for(i=0; i<n; i++){
            if(d[cod][i]!=1000000000){
                /// se poate ajunge in i
                for(j=0; j<n; j++){
                    if(a[i][j]){
                        bit=(1<<j);
                        val=a[i][j];
                        if( (cod & bit) == 0){
                            codnou=cod+bit;
                            d[codnou][j]=min(d[codnou][j], d[cod][i]+val);
                        }
                    }
                }
            }
        }
    }
    for(i=1; i<n; i++){
        if(a[i][0]){
            minim=min(minim, d[stop][i]+a[i][0]);
        }
    }
    fout<<minim;
}