#include <bits/stdc++.h>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");

const int MAXN = 20;
const int oo = 1000000000;
vector<vector<int>> c,d;
 int N,M,i,m,sol,C;
 vector<int> From,To;
int main()
{
    f>> N >> M;
    c=vector<vector<int>>(N,vector<int>(N,oo));

    for (i = 1; i <= M; ++i)
    {
        int x, y, z;
        f >> x >> y >> z;
        c[x][y] = z;
    }
    N--;
    C=1<<N;
    d=vector<vector<int>>(N,vector<int>(C,oo));
    for(i=0;i<N;i++)
        d[i][1<<i]=c[N][i];
    for(m=1;m<C-1;m++)
    {
        From.resize(0);To.resize(0);
        for(i=0;i<N;i++)
            if(m&(1<<i))
                From.push_back(i);
            else
                To.push_back(i);
        for(auto I:From)
            for(auto J:To)
                d[J][m|(1<<J)]=min(d[J][m|(1<<J)],d[I][m]+c[I][J]);
    }
    sol=oo;
    C--;
    for(i=0;i<N;i++)
      sol=min(sol,d[i][C]+c[i][N]);
    g<<sol;
    return 0;
}