#include <fstream>
#include <algorithm>
#define INF 1<<25

using namespace std;

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

int n,m,w[20][20],dp[1<<18][18];
int main()
{
    fin>>n>>m;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            w[i][j]=INF;
    for(int i=0;i<(1<<n);++i)
        for(int j=0;j<n;++j)
            dp[i][j]=INF;
    for(int i=1;i<=m;++i)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        w[x][y]=cost;
    }
    dp[1][0]=0;
    for(int i=2;i<(1<<n);++i)
        for(int j=1;j<n;++j)
            if(i&(1<<j))
                for(int k=0;k<n;++k)
                    if(i&(1<<k))
                        dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+w[k][j]);
    int rez=INF;
    for(int i=1;i<n;++i)
        rez=min(rez,dp[(1<<n)-1][i]+w[i][0]);
    fout<<rez;
    return 0;
}