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

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

vector<vector<pair<int, int>>>Adjacency;
vector<vector<long long>>pd;

int main() {
    int n, m;
    fin>>n>>m;
    Adjacency.resize(n);
    pd.resize(n);
    int nr_sub = 1<<n;
    for (int i=0; i<n; i++)
        pd[i].assign(nr_sub, 1e18);

    for (int i=1;i<=m;i++) {
        int x, y, c;
        fin>>x>>y>>c;
        Adjacency[y].push_back({x, c});
    }
    pd[0][1]=0;

    for (int s=1; s < nr_sub; s++)
        for (int i = 0; i<n;i++) {
            if ( s & (1<<i) )
                for (auto &j : Adjacency[i])
                    if ((s & (1<<j.first)) &&
                        pd[j.first][s^(1<<i)] < 1e18 &&
                        pd[j.first][s^(1<<i)] + j.second < pd[i][s])
                        pd[i][s]=min( pd[i][s], pd[j.first][s^(1<<i)] + j.second);
        }

    long long cost_min=1e18;
    for (auto &e : Adjacency[0])
        if (pd[e.first][nr_sub-1] < 1e18)
            cost_min=min(cost_min,pd[e.first][nr_sub-1]+e.second);

    if (cost_min == 1e18)
        fout << "Nu exista solutie\n";
    else
        fout << cost_min << '\n';



    return 0;
}