#include<fstream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
 
int n, m, sol;
vector<vector<int>> cost, best;
vector<int> *G;
 
void dinamica() {
 
    int i, j;
 
    best[1][0] = 0;
    for(i=0; i<(1<<n); ++i)
        for(j=0; j<n; ++j)
            if(i & (1<<j))
                for(auto it=G[j].begin(), it2=G[j].end(); it!=it2; ++it)
                    if(i & (1<<*it))
                        best[i][j] = min(best[i][j], best[i^(1<<j)][*it] + cost[*it][j]);
}
 
int main() {
 
    int i, j;
 
    fin>>n>>m;
    cost.resize(n, vector<int>(n, 1<<30));
    best.resize(1<<n, vector<int>(n, 1<<30));
    G = new vector<int>[n];
    while(m--) {
        f >> i >> j;
        G[j].push_back(i);
        f >> cost[i][j];
    }
 
    dinamica();
 
    sol = 1<<30;
    for(auto it=G[0].begin(), it2=G[0].end(); it!=it2; ++it)
        sol = min(sol, best[(1<<n)-1][*it] + cost[*it][0]);
 
    if(sol == 1<<30)
        fout<<"nu exista solutie";
    else
        fout<<sol;
 
    
 
    return 0;
}