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

int cost[NMAX][NMAX], C[superMAX][NMAX];
int N, M;
const int mult = 100000000;
vector<int> smeq[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<N; ++i)
        for (j=0; j<N; ++j)
            cost[i][j] = mult;*/

    for (i=0; i<M; ++i)
    {
        in>>a>>b>>c;
        cost[a][b] = c;
        smeq[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<smeq[j].size(); ++k)
                    if (i&(1<<smeq[j][k]))
                        C[i][j] = min(C[i][j], C[i^(1<<j)][smeq[j][k]] + cost[smeq[j][k]][j]);

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

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

    return 0;
}