#include "bits/stdc++.h"
using namespace std;
ifstream f ("hamilton.in");
ofstream g ("hamilton.out");
long long mu[20][20],dp[262150][20];
int main ()
{
    long long n,m,x,i,j,cost,min1,y;
    f>>n>>m;
    for (x=1;x<=m;x++)
    {
        f>>i>>j>>cost;
        i++;
        j++;
        mu[i][j]=cost;
    }
    for (x=1;x<(1<<n);x++)
    {
        for (y=1;y<=n;y++)
        {
            dp[x][y]=1000000000000000000;
        }
    }
    dp[1][1]=0;
    for (x=1;x<(1<<n);x++)
    {
        for (y=1;y<=n;y++)
        {
                for (j=1;j<=n;j++)
               {
                if (mu[y][j] && (x&(1<<(j-1)))==0)
                {
                    dp[(x|(1<<(j-1)))][j]=min(dp[(x|(1<<(j-1)))][j],dp[x][y]+mu[y][j]);
                }
               }
        }
    }
    min1=1000000000000000000;
    for (x=1;x<=n;x++)
    {
        if (mu[x][1]) min1=min(min1,dp[(1<<n)-1][x]+mu[x][1]);
    }
    g<<min1;
    f.close ();
    g.close ();
    return 0;
}