#include <fstream>
#include <vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,x,y,z;
vector<pair<int,int>> v[21];
int dp[1000001][19],mini=100000001;
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>x>>y>>z;
        v[y].push_back({x,z});
    }
    for(int masca=1;masca<(1<<n);masca++){
       for(int i=0;i<n;i++){
        dp[masca][i]=1000000001;
       }
    }
    dp[1][0]=0;
    for(int masca=1;masca<(1<<n);masca++){
        for(int i=0;i<n;i++){
            if((1<<i)&masca){
                for(auto u:v[i]){
                    if((1<<u.first)&masca){
                    dp[masca][i]=min(dp[masca][i],
                                     dp[masca-(1<<i)][u.first]+u.second);
                    }
                }
            }
        }
    }
    for(auto u:v[0]){
        mini=min(mini,dp[(1<<n)-1][u.first]+u.second);
    }
    if(mini==100000001){
        fout<<"Nu exista solutie";
        return 0;
    }
    fout<<mini;
    return 0;
}