#include <iostream>
#include <bits/stdc++.h>

using namespace std;


int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    vector<vector<int>> lista_ad_inversa(20);
    vector<vector<int>> costuri(20,vector<int>(20));
    vector<vector<int>> matrice(263000,vector<int>(20,-1));
    int n,m;
    fin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            costuri[i][j]=1e9;
    for(int i=0;i<m;i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        lista_ad_inversa[y].push_back(x);
        costuri[x][y]=cost;
    }
    for(int conf=0;conf<(1<<n);conf++)
    {
        for(int i=0;i<n;i++)
            matrice[conf][i]=1e9;
    }
    matrice[1][0]=0;
    for(int conf=1;conf<(1<<n);conf++)
        for(int i=0;i<n;i++)
    {
        if(conf & (1<<i)){
            for(int k=0;k<lista_ad_inversa[i].size();k++){
                int x = lista_ad_inversa[i][k];
                matrice[conf][i] = min(matrice[conf][i],matrice[conf-(1<<i)][x]+costuri[x][i]);
            }
        }
    }
    int res = 1e9;
    for(int i=1;i<n;i++)
        res = min(res,matrice[pow(2,n)-1][i]+costuri[i][0]);

    if(res == 1e9)
        fout<<"Nu exista solutie";
    else
        fout<<res;


   return 0;
}