#include <bits/stdc++.h>

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int cost[20][20],n,m;
int c[262150][20];
vector <int> a[21];
int calc(int start,int bit,int last)
{
    int j;
    if(c[bit][last]==-1)
    {
        c[bit][last]=INT_MAX/2;
        for(j=0; j<a[last].size(); j++)
        {
            if((bit&(1<<a[last][j])))
            {
                if (a[last][j] == start && ((bit ^ (1<<last)) != (1<<start))) continue;
                c[bit][last]=min(c[bit][last],calc(start,bit^(1<<last),a[last][j])+cost[a[last][j]][last]);
            }
        }
    }
    return c[bit][last];
}
int main()
{
    f>>n>>m;
    int i,j,x,y,cc,ans;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
        {
            cost[i][j]=INT_MAX;
        }
    for(i=1; i<=m; i++)
    {
        f>>x>>y>>cc;
        cost[x][y]=cc;
        a[y].push_back(x);
    }

    memset(c, -1, sizeof(c));
    c[1][0]=0;
    ans=INT_MAX;
    for(j=0; j<a[0].size(); j++)
    {
       // g<<calc(0,(1<<n)-1,a[0][j])<<" ";
        ans=min(ans,calc(0,(1<<n)-1,a[0][j])+cost[a[0][j]][0]);
    }
    g<<ans<<" ";
    return 0;
}