#include <fstream>
using namespace std;

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

struct muchie {int n, c; muchie *a;};

muchie *v[20], *p;
int graf[20][20];
bool viz[20];
int i, j, n, m, cp, cm, nd, x, y, c;

void dfs (int fx, int ndrm){
	muchie *fq=v[fx];
	
	if (ndrm==1){
		if (graf[fx][1]!=0 && graf[fx][1]+cp<cm) cm=graf[fx][1]+cp;
	}
	else{
		while (fq!=NULL){
			if (viz [fq->n]==0){
				viz[fq->n]=1; cp+=fq->c;
				dfs (fq->n, ndrm-1);
				viz [fq->n]=0; cp-=fq->c;
			}
			fq=fq->a;
		}
	}
}
			

int main(){
	cm=2000000000;
	
	f>>n>>m;
	for (i=1; i<=m; i++){
		f>>x>>y>>c;
		p=new muchie; p->n=y; p->c=c; p->a=v[x]; v[x]=p;
		graf[x][y]=c;
	}
	
	viz[1]=1;
	dfs(1, n);
	
	g<<cm;
}