#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

#define inf 2e9
int n,m,aux ;
int dp[1<<18][18];
vector <pair <int, int>> G[20];

int main()
{
    int a,b,cost;
    fin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        fin>>a>>b>>cost;
        G[b].push_back({a,cost});
    }
    for (int i=1; i<=(1<<n)-1; i++)
        for (int j=0; (1<<j)<=i; j++)
        {
            dp[i][j]=inf;
            dp[1][0]=0;
            if (i&(1<<j))
            {
                aux=i-(1<<j);
                for (auto it:G[j])
                    if (aux&(1<<it.first))
                        dp[i][j] = min (dp[i][j], dp[aux][it.first]+it.second);
            }
        }

    int rez=inf;
    for (auto it:G[0])
        rez = min (rez, dp[(1<<n)-1][it.first]+it.second);
    if (rez==inf)
        fout<<"Nu exista solutie\n";
    else
        fout<<rez;

    return 0;
}