#include <bits/stdc++.h>

#define INFINIT 0x3f3f3f3f

using namespace std;

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

int n, m;
vector <vector <int>> lista_adiacenta;

int main()
{
    vector <vector <pair<int, int>>> costuri_hamilton;
    fin>>n>>m;
    for(int i=1; i <=m; i++)
    {
        int x,y,ct;
        fin>>x>>y>>ct;
        costuri_hamilton[x].push_back({y, ct});
    }

    int cost_final = INFINIT;
    int costuri[(1<<n)+5][n+5];

    for(int i = 0; i < (1<<n); i++)
        for(int j = 0; j < n; j++)
            costuri[i][j] = INFINIT;

    costuri[1][0] = 0;

    for(int i=0; i <(1<<n); i++)
        for(int j=0; j<n; j++)
            for(int k=0; k<costuri_hamilton[j].size(); k++)
                costuri[i][j] = min(costuri[i][j], costuri[i ^(1<<j)][costuri_hamilton[j][k].first]+costuri_hamilton[j][k].second);

    for(int i=0; i<costuri_hamilton[0].size(); i++)
        cost_final = min(cost_final, costuri[(1<<n)-1][costuri_hamilton[0][i].first] + costuri_hamilton[0][i].second);

    if(cost_final != INFINIT)
        fout<<cost_final;
    else
        fout<<"Nu exista solutie";

    return 0;
}