#include <fstream>
#include <vector>

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
const int tigan=100000000;
vector <int> graf[20];
int n,m,i,j,x,y,sol;
int cost[20][20],c[262151][20],k;
int main()
{
    f>>n>>m;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            cost[i][j]=tigan;
        }
    }
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        graf[y].push_back(x);
        f>>cost[x][y];
    }
    for(i=0;i<(1<<n);i++)
    {
        for(j=0;j<n;j++)
        {
            c[i][j]=tigan;
        }
    }
    c[1][0]=1;
    for(int i=0;i<(1<<n);++i)
    {
        for(int j=0;j<n;++j)
        {
            if(i&(1<<j))
            {
                for(k=0;k<graf[j].size();++k)
                {
                    if(i&(1<<graf[j][k]))
                    {
                        c[i][j]=min(c[i][j],c[i^(1<<j)][graf[j][k]]+cost[graf[j][k]][j]);
                    }
                }
            }
        }
    }
    sol=tigan;
    for(i=0;i<graf[0].size();++i)
    {
        sol=min(sol,c[(1<<n)-1][graf[0][i]]+cost[graf[0][i]][0]);
    }
    if(sol==tigan)g<<"Nu exista solutie"<<'\n';
    else g<<sol-1<<'\n';
    return 0;
}