#include<fstream>
#include<cstring>
#include<vector>
#define inf 0x7f7f7f7f
using namespace std;
vector<pair<int, int> > L[18];
int x, y, z, n, m, stare, nod, vecin, cost, D[1<<18][18], M[18], i, sol, urmstare;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
int main()
{
    memset(D, 127, sizeof(D));
    memset(M, 127, sizeof(M));
    in>>n>>m;
    for(i=1; i<=m; i++)
    {
        in>>x>>y>>z;
        L[x].push_back(make_pair(y, z));
        if(y==0)
        {
            M[x]=z;
        }
    }
    D[1][0]=0;
    for(stare=1; stare<(1<<n); stare+=2)
    {
        for(nod=0; nod<n; nod++)
        {
            if(D[stare][nod]!=inf)
            {
                for(i=0; i<L[nod].size(); i++)
                {
                    vecin=L[nod][i].first;
                    cost=L[nod][i].second;
                    if((stare&(1<<vecin))==0)
                    {
                        urmstare=stare+(1<<vecin);
                        D[urmstare][vecin]=min(D[urmstare][vecin], D[stare][nod]+cost);
                    }
                }
            }
        }
    }
    sol=inf;
    for(i=1; i<n; i++)
    {
        if(M[i]!=inf && D[(1<<n)-1][i]!=inf)
        {
            sol=min(sol, D[(1<<n)-1][i]+M[i]);
        }
    }
    out<<sol;
    return 0;
}