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