#include <iostream>
#include <fstream>

using namespace std;

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

int st[20], k, n, m, v[20][20], pus[20];
long long s=0, smin = 29999999;


void init(int k) {
    st[k] = -1;
}

int succesor(int k) {
    if(st[k] < n) {
        st[k]++;
        return 1;
    }
    return 0;
}

int valid(int k) {
    if(k==n)if(v[st[n]][st[1]]==0)return 0;
    if(k == 1)
        return 1;
    if(!pus[st[k]] && v[st[k-1]][st[k]])
        return 1;
    return 0;
}

void solutie() {
    if(smin > s)
        smin = s;
    for(int i = 1; i <= n; i++) {

    }

}


void back(int k) {
    if(k == n + 1) {
        s += v[st[k-1]][st[1]];
        solutie();
        s -= v[st[k-1]][st[1]];
    }
    else {
    init(k);
        while(succesor(k)) {
            if(valid(k)) {
                s += v[st[k-1]][st[k]];
                pus[st[k]] = 1;
                back(k + 1);
                s -= v[st[k-1]][st[k]];
                pus[st[k]] = 0;
            }
        }
    }
}

int main()
{
    int i, x, y, c;
    in >> n >> m;
    for(i = 1; i <= m; i++) {
        in >> x >> y >> c;
        v[x][y] = c;
    }
    back(1);
    out << smin << "\n";
    in.close();
    out.close();
    return 0;
}