#include <bits/stdc++.h>

using namespace std;

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

using ll = long long;
const int NMAX(19);
int mat[NMAX][NMAX], dp[(1 << NMAX)][NMAX];

int main()
{
    int n, m;
    fin >> n >> m;

    for(int i = 1; i <= m; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;
        mat[x][y] = c;
    }

    for(int i = 0; i < n; ++i)
        for(int msk = 0; msk <= (1 << n); ++msk)
            dp[msk] [i]= 1e9;

    dp[1][0] = 0;
    for(int msk = 1; msk < (1 << n); ++msk)
    {
        for(int i = 0; i < n; ++i)
            if((1 << i) & msk)
                for(int j = 0; j < n; ++j)
                    if(mat[i][j] && !((1 << j) & msk))
                        dp[msk | (1 << j)][j] = min(dp[msk | (1 << j)][j], dp[msk][i] + mat[i][j]);
    }

    int minn = 1e9;
    for(int i = 1; i < n; ++i)
        if(mat[i][0] && dp[(1 << n) - 1][i] != 1e9)
            minn = min(minn, dp[(1 << n) - 1][i] + mat[i][0]);

    if(minn != 1e9)
        fout << minn<< '\n';
    else fout << "Nu exista solutie\n";
    return 0;
}