#define inf 100000000
#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
vector<pair <int,int> > M[20];
int C[30000][20];
int main()
{
    int n,i,x,y,c,m,j,vecin,cost,k,total;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        M[x].push_back({y,c});
    }
    x=1<<n;
    for(i=0; i<x;i++)
		for(j=0; j<n;j++) C[i][j] = inf;
    C[1][0]=0;
    for(k=1;k<x;k++) ///configuratii
        for(i=0;i<n;i++)  ///noduri
           if (k & (1<<i))
                {
                    for(j=0;j<M[i].size();j++) ///vecini
                       if(k & (1<<(M[i][j].first)))
                        {
                            vecin=M[i][j].first;
                            cost=M[i][j].second;
                            C[k][i]=min(C[k][i], C[k ^(1<<i)][vecin] + cost);
                        }
                }
    total=inf;
    for(i=0;i<M[0].size();i++)
        total=min(total, C[(1<<n)-1][M[0][i].first]+M[0][i].second);

    fout<<total;
    return 0;
}