#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<int, int>>> citireLisAdiacenta()
{
    ifstream fin("hamilton.in");
    vector<vector<pair<int,int>>> lisAdiacenta;
    int N, M;
    fin >> N >> M;
    lisAdiacenta.resize(N);

    for (int i = 1; i <= M; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        lisAdiacenta[x].push_back({y,c});
    }
    return lisAdiacenta;
}


int hamilton(vector<vector<pair<int,int>>> &lisAdiacenta)
{
    vector<vector<int> > dpCost(1 << lisAdiacenta.size(), vector<int>(lisAdiacenta.size(), 0x3f3f3f3f));
    int costTotal;

    dpCost[1][0] = 0;
    for (int i = 0; i < 1 << lisAdiacenta.size(); ++i) { //toate ciclurile
		for (int j = 0; j < lisAdiacenta.size(); ++j) {
			if (i & (1<<j)) {
				for (int k = 0; k < lisAdiacenta[j].size(); ++k){
					if (i & (1<<lisAdiacenta[j][k].first)) {
                        dpCost[i][j] = min(dpCost[i][j], dpCost[i ^ (1<<j)][lisAdiacenta[j][k].first] + lisAdiacenta[j][k].second);
					}
				}
			}
        }
    }
    costTotal = 0x3f3f3f3f;
	for (int i = 0; i < lisAdiacenta[0].size(); ++i) {
		costTotal = min(costTotal, dpCost[(1<<lisAdiacenta.size()) - 1][lisAdiacenta[0][i].first] + lisAdiacenta[0][i].second);
    }
    if(costTotal != 0x3f3f3f3f)
        return costTotal;
    else return -1;
}


int main()
{
    vector<vector<pair<int,int>>> lisAdiacenta = citireLisAdiacenta();
    int rezultat = hamilton(lisAdiacenta);

    ofstream fout("hamilton.out");
    if(rezultat != -1) {
        fout << rezultat;
    }
    else {
        fout << "Nu exista solutie";
    }
    return 0;
}