#include<fstream>
#include<vector>
using namespace std;
ifstream fin("hamilton.in"); ofstream fout("hamilton.out");
 
vector < pair<int,int> > G[18];
const int INF = 1 << 30;
int n, m, ad[18][18], dp[1 << 18][18]; // dp[i][j] = costul pentru submultimea i cu ultimul element j

void solve(){
    int i, j, k, adj, cost, submultime, total = (1 << n) - 1, costmin;
	
    for(i = 1; i <= total; i++)
        for(j = 0; j < n ; j++)
            dp[i][j]= INF;
	
    dp[1][0] = 0;
    
	for(i = 1; i <= total; i++)
        for(j = 0 ; j < n; j++)
            if(dp[i][j] != INF)
				for(k = 0; k < G[j].size(); k++){
					adj = G[j][k].first;
					cost = G[j][k].second;
					
					if(!((1 << adj) & i)){
						submultime = i + (1 << adj);
						dp[submultime][adj]= min(dp[submultime][adj], dp[i][j] + cost);
					}
				}
    
    for(costmin = INF, i = 0; i < n; i++)
        if(ad[i][0] && dp[total][i] + ad[i][0] < costmin)
            costmin = dp[total][i]+ ad[i][0];
	
    if(costmin == INF)
        fout<<"Nu exista solutie";
	else fout<<costmin;
}
 
int main(){
    int x, y, c, i;
    fin >> n >> m;

    for(i = 0; i < m; i++){
        fin >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
        ad[x][y] = c;
    }

    solve();
    return 0;
}