#include <fstream>
#include <vector>
#define nmax 28
#define mmax 275500
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int cost[nmax][nmax];
int c[mmax][nmax];
vector <int> graph[nmax];

int main()
{
    int n,m,x,y,infinute=100000002;
    fin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cost[i][j]=infinute;
    for(int i=0;i<1<<n;i++)
        for(int j=0;j<n;j++)
            c[i][j]=infinute;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        graph[y].push_back(x);
        fin>>cost[x][y];
    }
    c[1][0]=0;
    for(int i=0;i<1<<n;i++)
        for(int j=0;j<n;j++)
            if(i&(1<<j))
                for(int k=0;k<graph[j].size();k++)
                    if(i&(1<<graph[j][k]))
                        c[i][j]=min(c[i][j],c[i^(1<<j)][graph[j][k]]+cost[graph[j][k]][j]);
    int sol=infinute;
    for(int k=0;k<graph[0].size();k++)
        sol=min(sol,c[(1<<n)-1][graph[0][k]]+cost[graph[0][k]][0]);
    if(sol==infinute)
        fout<<"Nu exista solutie";
    else
        fout<<sol;
    return 0;
}