#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

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

const int Nmax =25;
int n, m, cost[Nmax][Nmax], DP[262150][Nmax], Min = 10000000;
vector <int> G[Nmax];

int Drum(int conf, int nod)
{
    if(DP[conf][nod] == -1)
    {
        DP[conf][nod] = 10000000;
        for(int i = 0; i < (int)G[nod].size(); i++)
            if(conf & (1<<G[nod][i]))
                DP[conf][nod] = min(DP[conf][nod], Drum(conf ^ (1<<nod), G[nod][i]) + cost[G[nod][i]][nod]);
    }
    return DP[conf][nod];
}

int main()
{
    f>>n>>m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cost[i][j] = 10000000;
    for(int i = 1; i <= m; i++)
    {
        int x,y;
        f>>x>>y;
        G[y].push_back(x);
        f>>cost[x][y];
    }
    memset(DP,-1,sizeof(DP));
    DP[1][0] = 0;
    for(int i = 0; i < (int)G[0].size(); i++)
    {
        Min = min(Min, Drum((1<<n)-1,G[0][i]) + cost[G[0][i]][0]);
    }
    if(Min == 10000000) g<<"nu exista sol\n";
    else g<<Min<<'\n';
    return 0;
}