//Balcau Ionut - grupa 134
// ciclu hamiltonian de cost minim
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n, m, sol;
vector< vector<int> > c, cm;
vector< int > g[20];

void citire(){
    int i, j;

    fin >> n >> m;
    c.resize(n, vector<int>(n, 1<<30));
    cm.resize(1<<n, vector<int>(n, 1<<30));
    while(m--) {
        fin >> i >> j;
        g[j].push_back(i);
        fin >> c[i][j];
    }
}

void solve() {
    vector<int>::iterator it;
    int i, j;
    cm[1][0] = 0;
    for(i=0; i<(1<<n); ++i)
        for(j=0; j<n; ++j)
            if(i & (1<<j))
                for(it=g[j].begin(); it!=g[j].end(); ++it)
                    if(i & (1<<*it))
                        cm[i][j] = min(cm[i][j], cm[i^(1<<j)][*it] + c[*it][j]);
}

int main() {

    

    solve();
    vector<int>::iterator it;
    sol = 1<<30;
    for(it=g[0].begin(); it!=g[0].end(); ++it)
        sol = min(sol, cm[(1<<n)-1][*it] + c[*it][0]);

    if(sol == 1<<30)
        fout << "nu exista solutie";
    else
        fout << sol;

    fin.close();
    fout.close();

    return 0;
}