#include <fstream>
#include <vector>
#define MAX 1000000000
using namespace std;

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

int n,m,cost[25][25],C[300000][25];
vector<int> nod[25];

int main()
{
    f >> n >> m;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++) cost[i][j] = MAX;
    for(int i=0; i<(1<<n); i++)
        for(int j=0; j<n; j++) C[i][j] = MAX;
    C[1][0] = 0;
    for(int i=1; i<=m; i++){
        int x, y, c;
        f >> x >> y >> c;
        nod[y].push_back(x);
        cost[x][y] = c;
    }
    for(int i=0; i<(1<<n); i++)
    {
        for(int j=0; j<n; j++)
            if(i & (1<<j)){
                for(int k=0; k<nod[j].size(); k++){
                    int var = nod[j][k];
                    if(i & (1<<var)){
                        C[i][j] = min(C[i][j], C[i^(1<<j)][var] + cost[var][j]);
                    }
                }
            }
    }
    int mini = MAX;
    for(int i=0; i<nod[0].size(); i++){
        mini = min(mini, C[(1<<n)-1][nod[0][i]] + cost[nod[0][i]][0]);
    }
    if(mini == MAX) g << "Nu exista solutie" << '\n';
      else g << mini << '\n';
    return 0;
}