#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][(1 << n) - 1] != INF && zero[i] != INF)
            sol = min(sol,
                      dp[i][(1 << n) - 1] + zero[i]);
    }
 
    g << sol;
 
    return 0;
}