#include <bits/stdc++.h>

using namespace std;

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

const int oo = 1e9;
int n, m;
int dp[1 << 18][20];
int v[20][20];

void Citire()
{
    int i, x, y, cost, stare, j, masca;
    fin >> n >> m;
    for(i = 1;i <= m;i++)
    {
        fin >> x >> y >> cost;
        v[x][y] = cost;
    }
    int N = (1 << n) - 1;
    for(stare = 0;stare <= N;stare++)
        for(i = 0;i < n;i++)
            dp[stare][i] = oo;
    dp[1][0] = 0;
    for(stare = 1;stare <= N;stare++)
        for(i = 0;i < n;i++)
        {
            if((stare & (1 << i)))
                for(j = 1;j < n;j++)
                    if((stare & (1 << j)) == 0)
                    {
                        masca = (stare | (1 << j));
                        if(v[i][j])
                            dp[masca][j] = min(dp[masca][j],
                                               dp[stare][i] + v[i][j]);
                    }
        }

    int sol = oo;
    for(i = 1;i < n;i++)
        if(v[i][0])
        {
            sol = min(sol, dp[N][i] + v[i][0]);
        }
    if(sol != oo)
        fout << sol << "\n";
    else
        fout << "Nu exista solutie";


}
int main()
{
    Citire();
    return 0;
}