#include <bits/stdc++.h>
using namespace std;
int n,m,x,y,z,i,j,k,dp[600000][20],cost[20][20],min1;
vector <int> v[20];
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    cost[i][j]=1000000007;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        cost[x][y]=z;
        v[y].push_back(x);
    }
    for(j=1;j<(1<<n);j++)
        for(i=0;i<n;i++)
            dp[j][i]=1000000007;
    dp[1][0]=1;
    for(j=1;j<(1<<n);j++)
    {
        for(i=0;i<n;i++)
        {
            if(j&(1<<i))
            {
                for(k=0;k<=v[i].size()-1;k++)
                {
                    if(j&(1<<v[i][k]))
                    {
                       // if(dp[j][i]==0)dp[j][i]=dp[j^(1<<i)][v[i][k]]+cost[v[i][k]][i];
                         dp[j][i]=min(dp[j][i],dp[j^(1<<i)][v[i][k]]+cost[v[i][k]][i]);
                    }
                }
            }
        }
    }
    min1=1000000007;
    for(i=0;i<=v[0].size()-1;i++)
    {
        if(min1>dp[(1<<n)-1][v[0][i]]+cost[v[0][i]][0])min1=dp[(1<<n)-1][v[0][i]]+cost[v[0][i]][0];
    }
    printf("%d",min1-1);
    return 0;
}