#include <fstream>
#include <vector>

#define pb push_back
#define mp make_pair

using namespace std;

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

int n,m;

const int N=19;
const int INF=1<<30;

vector <pair<int,int> > graph[N];

int ad[N+2][N+2];

int dp[1<<(N+2)][N+5]; // dp[i][j] costu pentru submultimea i cu ultimul element j

void read(){
	int x,y,c,i;
	in>>n>>m;
	for(i=1;i<=m;++i){
		in>>x>>y>>c;
		x++;
		y++;
		graph[x].pb(mp(y,c));
		ad[x][y]=c;
	}
}

void solve(){
	int i,j,k;
	int subtotal=0;
	for(i=1;i<=n;++i){
	    subtotal+=(1<<i);
	}
	for(i=1;i<=subtotal;++i){
		for(j=1;j<=n;++j){
			dp[i][j]=INF;
		}
	}
	dp[2][1]=0;
	int vecin,cost,submultime;
	for(i=1;i<=subtotal;++i){
		for(j=1;j<=n;++j){
		    if(dp[i][j]==INF)
                continue;
			for(k=0;k<graph[j].size();++k){
				vecin=graph[j][k].first;
				cost=graph[j][k].second;
				if(!((1<<vecin) & i)){
					submultime=i+ (1<<vecin);
					dp[submultime][vecin]=min(dp[submultime][vecin],dp[i][j]+cost);
				}
			}
		}
	}
	int costmin=INF;
	for(i=1;i<=n;++i){
		if(ad[i][1] && dp[subtotal][i] + ad[i][1]<costmin){
			costmin= dp[subtotal][i]+ ad[i][1];
		}
	}
	out<<costmin;
}

int main(){
	read();
	solve();
	return 0;
}