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

using namespace std;

int n, m, c[20][20], dp[300000][20],x,y,ult;

int maxv=0x3f3f3f3f;

vector<int> g[20];

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

void initialize()
{
    ult=(1<<n)-1;

    for (int i=0;i<=ult;i++)
        for (int j=0;j<n;j++)
            dp[i][j] = maxv;




}

void citire()
{
    f>>n>>m;
    int cost;
    for(int i=0;i<m;i++)
    {
        f>>x>>y>>cost;

        c[x][y]=cost;
        g[y].push_back(x);
    }

}

void solve()
{
    dp[1][0]=0;
    for (int i=1;i<=ult;i++)
        for (int j=1;j<n;j++)
            for (const auto& it: g[j])
                dp[i][j] = min(dp[i][j], dp[i^(1<<j)][it] + c[it][j]);

}

void afis()
{
    int rezult=maxv;
    for (const auto& it: g[0])
        rezult=min(rezult,dp[ult][it]+c[it][0]);
    if (rezult==maxv)
        fout<<"Nu exista solutie"<<'\n';
    else
        fout<<rezult<<'\n';

}

int main()
{
    citire();
    initialize();


    solve();
    afis();

    return 0;
}