#include <fstream>
#include <climits>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n, m, x, y, c, cost[20][20], inf;
long long d[1 << 20][20];
int main()
{
    inf = INT_MAX;
    fin >> n >> m;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cost[i][j] = inf;

    for(int i = 1; i <= n; ++i){
        fin >> x >> y >> c;
        cost[x][y] = c;
    }

    for(int i = 1; i <= ((1 << n) - 1); ++i)
        for(int j = 0; j < 20; ++j)
            d[i][j] = inf;
    d[1][0] = 0;
    for(int i = 1; i <= ((1 << n) - 1); ++i){
        for(int j = 0; j < n; ++j){
            if(i & (1 << j)){
                for(int k = 0 ; k < n; ++k)
                    if(i & (1 << k) && cost[k][j] != inf)
                        d[i][j] = min(d[i][j], d[i ^ j][k] + cost[k][j]);
            }
        }
    }

    long long mini = inf;
    for(int j = 0; j < n; ++j)
        mini = min(mini, d[(1 << n) - 1][j] + cost[j][0]);

    fout << mini;
    return 0;
}