#include <fstream>

#include <vector>

using namespace std;

ifstream fin("hamilton.in");

ofstream fout("hamilton.out");

const int NMax = 18;

const int oo = 1e9;

vector <int> G[NMax + 5];

int A[NMax + 5][NMax + 5];

int N,M,Sol=oo;

int DP[(1 << NMax) + 5][NMax + 5];

void Read()

{

    fin >> N >> M;



    for(int i  = 1; i <= M; ++i)

    {

        int x,y,c;

        fin >> x >> y >> c;

        G[y].push_back(x);

        A[x][y] = c;

    }

}



void Solve()

{

    for(int i = 0; i < (1 << N); ++i)

        for(int j = 0; j < N; ++j)

            DP[i][j] = oo;

    DP[1][0] = 0;

    for(int i = 1; i < (1 << N); ++i)

        for(int j = 0; j < N; ++j)

        {

            if(i & (1<<j))

                for(auto k : G[j])

                    if(i & (1<<k))

                        DP[i][j] = min(DP[i][j],DP[i^(1<<j)][k] + A[k][j]);

        }

}



void Print()

{



    for(auto i : G[0])

        Sol = min(Sol,DP[(1 << N)-1][i] + A[i][0]);

    if(Sol == oo)

        fout << "Nu exista solutie";

    else

        fout << Sol << "\n";

}

int main()

{

    Read();

    Solve();

    Print();

    return 0;

}