#include <bits/stdc++.h>
#define DIM 18

using namespace std;

ifstream fin("hamilton.in");

ofstream fout("hamilton.out");

int dp[1 << DIM][DIM + 1];

int n, m, x, y, ret, cost;

int a[DIM + 1][DIM + 1];

/*

    dp[i][j] = def = costul minim sa avem ajungem in nodul j trecand prin toate nodurile din masca i.

    O(2^N * N) timp si memorie

*/

int main(){

    fin >> n >> m;

    for(int i=1;i<=n;i++)

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

            a[i][j] = 1e9;

    while(m--){

        fin >> x >> y >> cost;

        ++x;

        ++y;

        a[x][y] = min(a[x][y], cost);

    }

    for(int mask=1;mask<(1<<n);mask++)

        for(int i=1;i<=n;i++)

            dp[mask][i] = 1e9;

    dp[1][1] = 0;

    for(int mask=2;mask<(1<<n);mask++){

        for(int i=1;i<=n;i++)

            if((mask >> (i - 1)) & 1){

                for(int j=1;j<=n;j++){

                    if(j != i && a[j][i] != 1e9 && dp[mask ^ (1 << (i - 1))][j] != 1e9)

                        dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << (i - 1))][j] + a[j][i]);

                }

            }

    }

    ret = 1e9;

    for(int i=1;i<=n;i++)

        ret = min(ret, dp[(1 << n) - 1][i] + a[i][1]);

    if(ret != 1e9)

        fout << ret;

    else fout << "Nu exista solutie";

    return 0;



}