#include <bits/stdc++.h>
#define oo 5555555

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int dp[18][(1<<18)];
int a[20][20];
int n,m;
int N;

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        a[x][y]=c;
    }
    N=(1<<n);
    for(int i=0;i<n;i++)
        for(int masca=0;masca<N;masca++)
            dp[i][masca]=oo;
    dp[0][1]=0;
    for(int masca=3;masca<N;masca+=2)
        for(int i=1;i<n;i++)
            if((masca&(1<<i)))
            {
                int x=masca^(1<<i);
                for(int j=0;j<n;j++)
                    if((x&(1<<j)) && a[j][i]>0)
                        dp[i][masca]=min(dp[i][masca],
                                         dp[j][x]+a[j][i]);
            }
    int mn=1e9;
    for(int i=1;i<n;i++)
        if(mn>(dp[i][N-1]+a[i][0]) && a[i][0]>0)
            mn=dp[i][N-1]+a[i][0];
    fout<<mn<<"\n";
    return 0;
}