#include <fstream>

using namespace std;

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

int mat[19][19];
int dp[262144][19];
/**
dp[masca][i] retine costul minim pentru a ajunge in nodul i vizitand exact nodurile din masca
*/

int main(){

    int n, m;

    in >> n >> m;

    for(int i = 0; i < n ; i++)
        for(int j = 0; j < n; j++)
            mat[i][j] = 1000000000;

    for(int i = 1; i <= m; i++){
        int x, y, c;
        in >> x >> y >> c;
        mat[x][y] = c;
    }

    for(int j = 1; j < (1 << n); j++)
        for(int i = 0; i < n; i++)
            dp[j][i] = 1000000000;

    dp[1][0] = 0;

    for(int stare = 0; stare < (1 << n); stare++){  /// parcurg toate combinatiile de noduri vizitate (submultimile nodurilor)
        for(int i = 0; i < n; i++){ /// nodul in care ma aflu in acest moment
            if(stare & (1 << i)) /// verific daca nodul i este inclus in masca 'stare'
                for(int j = 0; j < n; j++) /// un nod anterior j in drum
                    if(stare & (1 << j))
                        dp[stare][i] = min(dp[stare][i], dp[stare ^ (1 << i)][j] + mat[j][i]);
            }
    }


    int sol = 1000000000;

    for(int i = 0; i < n; i++)
        sol = min(sol, dp[(1 << n) - 1][i] + mat[i][0]);

    if(sol == 1000000000) out << "Nu exista solutie";
    else out << sol;

    return 0;
}