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

using namespace std;

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

const int nmax = 18, inf = 0x3f3f3f3f;

vector <int> g[nmax + 5];
int n, m, cost[nmax + 5][nmax + 5], d[(1 << nmax) + 5][nmax];

void Read(){
    fin >> n >> m;
    int x, y, c;
    while (m--){
        fin >> x >> y >> c;
        g[y].push_back(x);
        cost[x][y] = cost[y][x] = c;
    }
}

void Solve(){
    for (int conf = 0; conf < (1 << n); conf++)
        for (int j = 0; j < n; j++)
            d[conf][j] = inf;
    d[1][0] = 0;
    for (int conf = 1; conf < (1 << n); conf++)
        for (int j = 0; j < n; j++)
            if (conf & (1 << j))
                for (auto vecin : g[j])
                    if (conf & (1 << vecin))
                        d[conf][j] = min(d[conf][j], d[conf - (1 << j)][vecin] + cost[j][vecin]);
}

void Print(){
    int x = (1 << n) - 1, Min = inf;
    for (int j = 0; j < n; j++)
        Min = min(Min, d[x][j] + cost[0][j]);
    if (Min == inf)
        fout << "Nu exista solutie" << '\n';
    else
        fout << Min << '\n';
}

int main(){
    Read();
    Solve();
    Print();
    return 0;
}