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

using namespace std;

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

const int NMAX  = 18;
const int STARI = (1 << NMAX);
const int INF = (1 << 20);

int n, m, dp[NMAX][STARI], zero[NMAX];
vector < pair < int, int > > G[NMAX];

int main() {

    f >> n >> m;

    for(int i = 0;i < n;++i)
        zero[i] = INF;

    for(;m--;) {
        int u, v, c;
        f >> u >> v >> c;

        G[u].push_back({v, c});

        // nodurile care intra in 0
        if(v == 0)
            zero[u] = c;
    }

    const int stari = (1 << n);

    for(int i = 0;i < n;++i)
        for(int j = 0;j < stari;++j)
            dp[i][j] = INF;

    // ciclu incepe din 0 si contine numai starea 1(b2) care inseamna ca pathul contine numai 1
    dp[0][1] = 0;
    for(int stare = 1;stare < stari;++stare) {
        for(int node = 0;node < n;++node) {
            if(dp[node][stare] != INF) {
                // din starea curenta trebuie sa trec in alta stare
                // starea curenta ex 10101011(2) care se termina in nodul "node"

                // trebuie sa parcurg vecinii nodului
                for(const auto& it : G[node]) {
                    int neighbor = it.first;
                    int cost     = it.second;

                    // daca stare curenta in care ne aflam nu contine nodul "neighbor"
                    if( (stare & (1 << neighbor)) == 0) {
                        int urmStare = stare + (1 << neighbor); // starea noua creata
                        dp[neighbor][urmStare] = min(dp[node][stare] + cost,
                                                     dp[neighbor][urmStare]);
                    }
                }
            }
        }
    }

    int sol{ INF };
    for(int i = 1;i < n;++i) {
        if(dp[i][stari] != INF && zero[i] != INF)
            sol = min(sol,
                      dp[i][stari] + zero[i]);
    }

    g << sol;

    return 0;
}