#include<fstream> 
#include<vector> 
#define DIM 18
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std; 
ifstream in("hamilton.in");
ofstream out("hamilton.out"); 

int costmin = INF, cost, next_nod, sursa, co, minim; 
int N, M, Tr[DIM], V[DIM];
vector< pair< int, int>  > G[DIM]; 
bool viz[DIM];

void parcurge(int sursa)
{
	int j;
	co = 0;
	for(j = 0; j < N; j++)	
        viz[j] = 0;	
	viz[sursa] = 1;
	Tr[0] = sursa; 
	
	for(j = 0; j < N-1; j++) 
	{
		int nod = Tr[j];
		minim = INF; 
	    for(vector<pair< int, int> >:: iterator it = G[nod].begin(); it != G[nod].end(); ++it)
			if( minim > it -> second && !viz[it -> first] ) 
		    {
			   minim = it -> second; 
			   next_nod = it -> first; 
		    }
			
	viz[next_nod] = 1;
	co += minim;
	Tr[j+1] = next_nod;
	}
    
	co += G[Tr[N-1]][sursa].second;
    
}
int main()
{
	int i, x, y, c;
	
	in >> N >> M; 
	for(i = 1; i <= M; i++)
	{
		in >> x >> y >> c; 
		G[x].pb(make_pair(y,c)); 
	}
	
	for(i = 0; i < N; i++)
	{
		sursa = i;
		parcurge(i);
		if( costmin > co )
			costmin = co;
	}

	
		out << costmin;
		
		return 0;
}