#include <bits/stdc++.h>

const int oo=1e9;

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n,m,x,y,c,i,j,k,dist[20][20],dyn[1<<20][20][20];
priority_queue<pair<pair<int,int>,pair<int,int> > > Q;
vector<pair<int,int> > v[20];

int main()
{
    f>>n>>m;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            dist[i][j]=oo;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        dist[x][y]=c;
        v[x].push_back({y,c});
    }
    int x=(1<<n)-1;
    for(i=0;i<=x;i++)
        for(j=0;j<n;j++)
            for(k=0;k<n;k++)
                dyn[i][j][k]=oo;
    for(i=0;i<n;i++)
    {
        Q.push({{0,0},{i,i}});
        dyn[0][i][i]=0;
    }
    while(Q.size())
    {
        pair<pair<int,int>,pair<int,int> > nod=Q.top();
        int mask=nod.first.second,poz=nod.second.first,pozinit=nod.second.second;
        Q.pop();
        if(dyn[mask][poz][pozinit]!=-nod.first.first)
            continue;
        for(auto it:v[poz])
            if((!(mask&(1<<it.first)))&&(it.first!=pozinit))
                if(dyn[mask|(1<<it.first)][it.first][pozinit]>dyn[mask][poz][pozinit]+it.second)
                {
                    dyn[mask|(1<<it.first)][it.first][pozinit]=dyn[mask][poz][pozinit]+it.second;
                    Q.push({{-dyn[mask|(1<<it.first)][it.first][pozinit],mask|(1<<it.first)},{it.first,pozinit}});
                }
    }
    int ans=oo;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(i!=j)
                ans=min(ans,dyn[x^(1<<i)][j][i]+dist[j][i]);
    g<<ans;
    return 0;
}