#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

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

vector<pair<int, int>> v[20];
vector<pair<int, int>> V[20];
int dp[(1<<18)][20];

int cost(bitset<20> &bit, int crr) {

    if(dp[bit.to_ulong()][crr] != 0)
        return dp[bit.to_ulong()][crr];

    int mi = 20000000;

    if(bit.to_ulong() == 0) {
        if(crr == 0)
            return 0;
        return 20000000;
    }

    for(int i = 0; i < V[crr].size(); i++) {

        if(bit[V[crr][i].first] == 0)
            continue;

        bit[V[crr][i].first] = 0;
        mi = min(mi, cost(bit, V[crr][i].first)+V[crr][i].second);
        bit[V[crr][i].first] = 1;

    }

    dp[bit.to_ulong()][crr] = mi;
    //cout << "TEST " << bit.to_ulong() << " " << crr << " " << dp[bit.to_ulong()][crr] << '\n';
    return mi;

}

int main() {

    int n,m;
    in >> n >> m;
    int x,y,z;

    for(int i = 1; i <= m; i++) {
        in >> x >> y >> z;
        v[x].push_back({y, z});
        V[y].push_back({x, z});
    }

    bitset<20> p;

    for(int j = 0; j < n; j++)
        p[j] = 1;

    int f = cost(p, 0);

    if(f == 20000000)
        out << "Nu exista solutie";
    else
        out << cost(p, 0);

    return 0;

}