#include <fstream>
#include <vector>
#define NMAX 20
using namespace std;

const int mult = 1<<30;
const int superMAX = (1<<18) + 10;
int cost[NMAX][NMAX], C[superMAX][NMAX];
int N, M;

vector<int> G[NMAX];

int main()
{
    ifstream in("hamilton.in");
    ofstream out("hamilton.out");
    int i, j, k, a, b, c;
    in>>N>>M;

    for (i=0; i<M; ++i)
    {
        in>>a>>b>>c;
        cost[a][b] = c;
        G[b].push_back(a);
    }

    for (i=0; i<1<<N; ++i)
        for (j=0; j<N; ++j)
            C[i][j] = mult;
    C[1][0] = 0;

    for (i=0; i<1<<N; ++i)
        for (j=0; j<N; ++j)
            if (i & 1<<j)
                for (k=0; k<G[j].size(); ++k)
                    if (i&(1<<G[j][k]))
                        C[i][j] = min(C[i][j], C[i^(1<<j)][G[j][k]] + cost[G[j][k]][j]);

    int result = mult;
    for (i=0; i<G[0].size(); ++i)
        result = min(result, C[(1<<N)-1][G[0][i]] + cost[G[0][i]][0]);

    if (result == mult) out<<"Nu exista solutie\n";
    else out<<result<<"\n";

    return 0;
}