#include <fstream>
#include <vector>
#define inf 0x3f3f3f3f
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n, m;
int dp[19][270000], cost[25][25];
int solve(int i, int j)
{
    if(dp[i][j]==-1) {
        dp[i][j] = inf;
        if ((1 << i) + 1 == j) {
            dp[i][j] = cost[0][i];
            return dp[i][j];
        }
        for (int x = 0; x < n; x++)
            if (cost[x][i])
                if ((j & (1 << x)) != 0)
                    dp[i][j] = min(solve(x, j ^ (1 << i)) + cost[x][i], dp[i][j]);
    }
    return dp[i][j];
}
int main() {

    //cit
    fin>>n>>m;
    int x, y, c;
    while(fin>>x>>y>>c)
        cost[x][y]=c;
    //init dp
    for(int i=0; i<=n; i++)
        for(int j=1; j<270000; j++)
            dp[i][j]=-1;
    int vmin=inf, full=(1<<n)-1;
    for(x=0; x<n; x++)
        if(cost[x][0])
            vmin=min(vmin, solve(x, full)+cost[x][0]);
    if(vmin==inf)
        fout<<"Nu exista solutie";
    else fout<<vmin;
    return 0;
}