#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

//solutie 20p O(N!)
const int nmax = 20;
int n,m,valmin = INT_MAX;
vector<vector<pair<int,int>>> mat(nmax,vector<pair<int,int>> (nmax));
vector<int> ans,nodes,costs(nmax*(nmax-1)+10);
void read_input(){
	fin >> n >> m;
	int nod_1,nod_2,cost;
	for(int i = 1; i <=m; i++){
		fin >> nod_1 >> nod_2 >> cost;
		mat[nod_1][nod_2] = make_pair(1,cost);
		costs[i] = cost;
	}
};
void solve(){
	for(int i = 0; i <=n-1; i++){
		nodes.push_back(i);
	};
	do{
	    int ok = 1,suma = 0;
	    for(int i =0; i <= n-2 && ok;i++){
			if(!mat[nodes[i]][nodes[i+1]].first){ok = 0;}
			suma += mat[nodes[i]][nodes[i+1]].second;
	    }
	    if(!mat[nodes[n-1]][0].first){ok = 0;}
	    suma += mat[nodes[n-1]][0].second;
	    if(ok){
	    if(valmin > suma){
			valmin = suma;
			ans = nodes;
	    }}
	}while(next_permutation(nodes.begin(),nodes.end()));
	
	fout << valmin;
	/*for(auto x : ans){cout << x << " ";}
	cout << *ans.begin();*/
}
int main(){
	read_input();
	solve();
	return 0;
}