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

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

int oo=2000000007;
int n, m;
vector <pair <int, int>> v[20];
int dp[1<<18][18];
int x, y, cost, newi;

/// dp[i][j] = costul minim sa ajung in j trecand prin nodurile care sunt
/// bitii de 1 ai lui i in binar  (i repr un drum in graf, pentru a verifica daca nodul k
/// este in acel drum facem i&(1<<k), daca rez e 0 => k nu e prin nodurile lui i, else k e printre nodurile lui i)

int main()
{
    f >> n >> m;
    for (int i=1; i<=m; i++) {
        f >> x >> y >> cost;
        v[y].push_back({x, cost}); /// G[i] = muchiile care 'intra' in i (celalalt capat si costul)
    }

    for (int i=1; i<=(1<<n)-1; i++) {  /// pt fiecare path
        for (int j=0; (1<<j)<=i; j++) {  /// pt fiecare nod din i
            dp[i][j] = oo;
            dp[1][0] = 0;
            if (i & (1<<j)) {    /// verificam daca j este printre nodurile lui i
                newi = i - (1<<j); /// stergem momentan nodul j din i
                for (auto it:v[j]) {   /// pentru toate muchiile care intra in j si celalalt nod e in newi
                    if (newi & (1<<it.first)) {
                        dp[i][j] = min(dp[i][j], dp[newi][it.first] + it.second); /// daca e mai bine sa vin din it.first, actualizez
                    }
                }
            }
        }
    }
    /// construim rezultatul, ne intereseaza drumurile care contin toate nodurile din dp ( linia dp[(1<<n)-1] )
    int rez = oo;
    for (auto it:v[0]) {
        rez = min(rez, dp[(1<<n)-1][it.first] + it.second);
    }
    if (rez == oo) {
        g << "Nu exista solutie";
    }
    else {
        g << rez;
    }
    return 0;
}