#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

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

vector<pair<int, int>> v[20];
vector<pair<int, int>> V[20];

int cost(bitset<20> &bit, int crr) {

    int mi = 20000000;

    if(bit.to_ulong() == 0)
        return 0;

    //cout << "TEST " << bit.to_ulong() << " " << crr << '\n';

    for(int i = 0; i < V[crr].size(); i++) {

        if(bit[V[crr][i].first] == 0)
            continue;

        bit[V[crr][i].first] = 0;
        mi = min(mi, cost(bit, V[crr][i].first)+V[crr][i].second);
        bit[V[crr][i].first] = 1;

    }

    return mi;

}

int main() {

    int n,m;
    in >> n >> m;
    int x,y,z;

    for(int i = 1; i <= m; i++) {
        in >> x >> y >> z;
        v[x].push_back({y, z});
        V[y].push_back({x, z});
    }

    bitset<20> p;

    for(int j = 0; j < n; j++)
        p[j] = 1;

    out << cost(p, 0);

    return 0;

}