#include <fstream>
using namespace std;

//////////////////////////

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

const int MAX = (1<<18);

const int inf = 18e6;

int dp[MAX][18] , c[18][18] , n , m , a , b , cost;

/////////////////////////

/*

    dp[masca][j] = lantul de cost minim incepand de la 1 si terminandu-se in j cu

    toate nodurile care au bitii setati in starea masca

*/

int main()
{

    cin >> n >> m;

    for(int i = 1 ; i <= m ; i++){

        cin >> a >> b >> cost;

        c[a][b] = cost;
    }

    int full = (1<<n)-1;

    // initializare

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

    dp[1][0] = 0;

    for(int mask = 1 ; mask <= full ; mask++){

        for(int i = 0 ; i < n ; i++){

            if(dp[mask][i] != inf){

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

                    if( i != j && c[i][j] && !(mask&(1<<j))){

                        dp[(mask | (1<<j))][j] = min(dp[(mask | (1<<j))][j] ,dp[mask][i] + c[i][j]);
                    }
                }
            }
        }
    }

    int ans = inf;

    for(int i = 0 ; i < n ; i++){

        if(c[i][0]) ans = min(ans,dp[full][i] + c[i][0]);
    }

    if( ans == inf ) cout << "Nu exista solutie";
    else cout << ans;

    return 0;
}