#define INF 0x3f3f3f3f
#define NMAX 20
#include <fstream>
using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n, m;
const int MMAX = (1<<18) + 5;
int cost[NMAX][NMAX], dp[NMAX][MMAX];

void init()
{
    int put2n = (1<<n);
    for(int i = 0; i<n; ++i)
    {
        for(int j=0; j<n; ++j)
            cost[i][j] = INF;

        for(int j = 0; j < put2n; ++j)
            dp[i][j] = -1;

    }
}




void read()
{
    int x, y, c;

    f>>n>>m;
    init();
    for(int i=0; i<m; ++i)
    {
        f>>x>>y>>c;
        cost[x][y] = c;
    }
}


int solve(int i, int j)
{
    if(dp[i][j] == -1)
    {
        dp[i][j] = INF;
        if(1 + (1<<i) == j) // am ajuns la final - sa am in multimea j doar elementul actual si cel de start (aici pe poz 1)
        {
            dp[i][j] = cost[0][i];
            return dp[i][j];
        }
        else for(int x = 1; x < n ; ++x)
            if(cost[x][i] != INF && ((1<<x) & j)) // daca de la x pot ajunge in i si x se afla in multimea actuala
                dp[i][j] = min(dp[i][j], solve(x, j ^ (1<<i)) + cost[x][i]); // min dintre actual si rezultatul oferit de drumul pana la x
                                                                             // de multime j fara i (inca nu am ajuns la i, practic merg un pas inainte)

    }
    return dp[i][j];
}

///4 3 2 1 0
///0 1 1 0 1


void write()
{
    int vmin = INF, full = (1<<n)-1;
    for(int x = 0; x < n; ++x)
        if(cost[x][0] != INF)
            vmin = min(vmin, solve(x, full) + cost[x][0]);
    if(vmin != INF)
        g<<vmin;
    else g<<"Nu exista solutie";

}


int main()
{
    read();
    write();
    return 0;
}