#include <fstream>
#include <vector>

#define Nmax 18
#define Cmax (1 << Nmax)
#define oo (1 << 30)
#define neighbour Graph[lastNode][i]

using namespace std;

vector <int> Graph[Nmax];
int N, Answer, Cost[Nmax][Nmax], A[Cmax][Nmax];

int hamila(int config, int lastNode) {

    if(A[config][lastNode] == 0) {

        A[config][lastNode] = oo;
        for(int i = 0; i < Graph[lastNode].size(); i++)
            if(((1 << neighbour) & config) != 0 && (neighbour != 0 || config == 1))
                A[config][lastNode] = min(A[config][lastNode], hamila(config ^ (1 << neighbour), neighbour) + Cost[neighbour][lastNode]);

    }

    return A[config][lastNode];
}
void Solve() {

    int i, node, startConfig;

    Answer = oo;
    startConfig = (1 << N) - 1;
    A[0][0] = 1;

    for(i = 0; i < Graph[0].size(); i++) {
        node = Graph[0][i];
        Answer = min(Answer, hamila(startConfig ^ (1 << node), node) + Cost[node][0] - 1);
    }

}
void Read() {

    int x, y, cost, M;
    ifstream in("hamilton.in");
    in >> N >> M;

    while(M--) {
        in >> x >> y >> cost;
        Graph[y].push_back(x);
        Cost[x][y] = cost;
    }

    in.close();
}
void Write() {

    ofstream out("hamilton.out");
    out << Answer << '\n';
    out.close();
}
int main() {

    Read();
    Solve();
    Write();

    return 0;
}