#include <iostream>
#include <fstream>
#include <vector>
//#include <climits>
#define lmax 100000000
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int cost[21][21];
int sol[1<<20][21],n,m;
vector<int> a[21];
int main()
{
    f>>n>>m;
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    cost[i][j]=lmax;
    for(int i=1;i<=m;i++)
    {
        int x1,x2;
        f>>x1>>x2;
        a[x2].push_back(x1);
        f>>cost[x1][x2];
    }
    for(int i=0;i< (1<<n);i++)
        for(int j=0;j<n;j++)
        sol[i][j]=lmax;
    sol[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<a[j].size();k++)
                if(i& (1<<a[j][k]))
                sol[i][j]=min(sol[i][j], sol[i ^ (1<<j)][ a[j][k] ] + cost[ a[j][k] ][j]);
    int rez=lmax;
    for(int i=0;i<a[0].size();i++)
        rez=min(rez, sol[(1<<n) - 1][ a[0][i] ] + cost[ a[0][i] ][0]);
    if(rez==lmax) g<<"Nu exista solutie";
        else g<<rez;
    return 0;

}