#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

#define inf 0x3f3f3f3f

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

int dst[262150][20], c[20][20], sol, n, m, x, y;
vector<int>g[20];

inline int Mem(int conf, int lastNode)
{
    if (dst[conf][lastNode]==-1)
    {
        dst[conf][lastNode]=inf;
        for(vector<int>::iterator it=g[lastNode].begin(); it<g[lastNode].end(); it++ )
        {
            if(conf&(1<<*it))
            {
                if(*it==0 && conf != ((1<<lastNode)+1) )
                    continue;
                dst[conf][lastNode]=min(dst[conf][lastNode],Mem(conf^(1<<lastNode),*it)+c[*it][lastNode]);
            }
        }
    }
    return dst[conf][lastNode];
}

int main()
{
    fin>>n>>m;
    for(int i = 0; i< n; i++ )
        for(int j = 0; j < n; j++ )
            c[i][j]=inf;
    memset(dst,-1,sizeof(dst));
    for(int i = 1; i<= m; i++ )
    {
        fin>>x>>y;
        fin>>c[x][y];
        g[y].push_back(x);
    }
    sol=inf;
    dst[1][0]=0;
    for(vector<int>::iterator it=g[0].begin(); it<g[0].end(); it++ )
        sol = min(sol,Mem((1<<n)-1,*it)+c[*it][0]);
    fout<<sol;
    fin.close();
    fout.close();
    return 0;
}