#include <fstream>
#define inf 1e9
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
int n,m,x,y,sol,dp[(1<<18)][19],c[19][19];
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>x>>y>>c[x][y];
    for(int mask=1;mask<(1<<n);mask++)
        for(int i=0;i<n;i++)
            dp[mask][i]=inf;
    dp[1][0]=0;
    for(int mask=1;mask<(1<<n);mask++)
        for(int i=0;i<n;i++)
            if((mask>>i)&1)
                for(int j=0;j<n;j++)
                    if(i!=j&&((mask>>j)&1)&&dp[mask][j]>dp[mask-(1<<j)][i]+c[i][j]&&c[i][j]!=0)
                        dp[mask][j]=dp[mask-(1<<j)][i]+c[i][j];
    sol=inf;
    for(int i=1;i<n;i++)
        if(c[i][0]!=0)
            sol=min(sol,dp[(1<<n)-1][i]+c[i][0]);
    cout<<sol;
    return 0;
}