#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#define G(i,j) ((i>>(j))&1)
#define S(i,j) (i^(1<<(j)))

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(int &bit, int crr) {

    //cout << bit << " " << crr << '\n';

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

    int mi = 20000000;

    if(bit == 0)
        return 0;

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

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

        bit = S(bit,V[crr][i].first);

        if(bit != 0 && V[crr][i].first == 0) {
            bit = S(bit,V[crr][i].first);
            continue;
        }

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

    }

    dp[bit][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});
    }

    int p=0;

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

    int f = cost(p, 0);

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

    return 0;

}