#include <bits/stdc++.h>
#define LIM 1<<17
/// TONI BO$$ was here
/// #MLC

using namespace std;

int dp[1<<18][18],a[18][18];

struct stare
{
    int nod,dr,cost;
    bool operator <(const stare &other) const
    {
        return cost>other.cost;
    }
};

priority_queue < stare > Q;

int main()
{
    int n,m,i,j,x,y,c,w,rez;
    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++)
            a[i][j]=INT_MAX/2;
    for(i=0; i<m; i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        a[x][y]=c;
    }
    for(i=0; i<n; i++)
        for(j=0; j<(1<<n); j++)
            dp[j][i]=INT_MAX/2;
    dp[1][0]=0;
    Q.push({0,1,0});
    while(!Q.empty())
    {
        stare z=Q.top();
        Q.pop();
        for(w=0; w<n; w++)
            if((z.dr^(1<<w))>z.dr && dp[z.dr^(1<<w)][w]>dp[z.dr][z.nod]+a[z.nod][w])
            {
                dp[z.dr^(1<<w)][w]=dp[z.dr][z.nod]+a[z.nod][w];
                Q.push({w,z.dr^(1<<w),dp[z.dr^(1<<w)][w]});
            }
    }
    rez=INT_MAX/2;
    for(i=1; i<n; i++)
        if(dp[(1<<n)-1][i]+a[i][0]<rez)
            rez=dp[(1<<n)-1][i]+a[i][0];
    printf("%d",rez);


    return 0;
}