#include <fstream>
#include <vector>

#define nMax 18
#define maskMax 262150
#define INF 1000000000
#define pb push_back

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n, m, Sol, Cost[nMax][nMax], C[maskMax][nMax];
vector<int> G[nMax];
void read()
{
    int x, y, z;
    fin>>n>>m;
    Sol=INF;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            Cost[i][j]=INF;
    for(int i=0;i < (1 << n);i++)
        for(int j=0;j<n;j++)
            C[i][j]=-1;

    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        G[y].pb(x);
        Cost[x][y]=z;
    }
    C[1][0]=0;
}
int memo(int conf,int last)
{
    if(C[conf][last]==-1)
    {
         C[conf][last]=INF;
         for(vector<int>::iterator it=G[last].begin();it!=G[last].end();it++)
         {
             int fiu=*it;
             if(conf & (1 << fiu))
             {
                 if(fiu==0 && conf!=((1<< last)+1))
                    continue;
                C[conf][last]=min(C[conf][last], memo((conf^(1 << last)), fiu)+Cost[fiu][last]);
             }
         }
    }
    return C[conf][last];
}
void solve()
{
    for(vector<int>::iterator it=G[0].begin();it!=G[0].end();it++)
    {
        int fiu=*it;
        Sol=min(Sol, memo((1 << n)-1, fiu)+Cost[fiu][0]);
    }
}
void write()
{
    fout<<Sol;
}
int main()
{
    read();
    solve();
    write();
    return 0;
}