#include <fstream>
#include <vector>

using namespace std;

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

const int nmax=18, n2max=(1<<nmax), inf=(1<<30)-1;

struct str{
    int x,y;
};

vector <str> g[nmax+1];

int d[nmax+1][n2max];

int main(){
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        fin>>x>>y>>z;
        str aux;
        aux.x=y;
        aux.y=z;
        g[x].push_back(aux);
    }
    int n2=(1<<n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n2;j++){
            d[i][j]=inf;
        }
    }
    d[0][1]=0;
    for(int j=1;j<n2;j+=2){
        for(int i=0;i<n;i++){
            int i2=(1<<i);
            if((j&i2)!=0){
                for(int k=0;k<int(g[i].size());k++){
                    int in=g[i][k].x;
                    int in2=(1<<in);
                    if((in2&j)==0){
                        if(d[in][j+in2]>d[i][j]+g[i][k].y){
                            d[in][j+in2]=d[i][j]+g[i][k].y;
                        }
                    }
                }
            }
        }
    }
    int sol=inf;
    for(int i=0;i<n;i++){
        for(int k=0;k<int(g[i].size());k++){
            if(g[i][k].x==0){
                int x=d[i][n2-1]+g[i][k].y;
                if(sol>x){
                    sol=x;
                }
            }
        }
    }
    fout<<sol<<"\n";
    return 0;
}