#include<iostream>
#include<vector>
#include<queue>
#include<fstream>
#include<algorithm>
#include<climits>
#include<set>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m;
vector<vector<int>> adq;
vector<vector<int>> maskMatrix;

int minCicluHamilton(){

    //matricea costurilor pentru fiecare ciclu posibil este si ea setata la maxim
    maskMatrix.assign((1<<n), vector<int>(n,INT_MAX));

    // cum cautam un ciclu hamiltonian nu conteaza de unde incepem,
    // mask - ul trebuie doar sa fie putere a lui 2 si nodul sa fie indexul corespunzator al bitului
    maskMatrix[1][0] = 0;

    /*
     maskMatrix[2][1] = 0;
     maskMatrix[4][2] = 0;
     maskMatrix[8][3] = 0;
     maskMatrix[16][4] = 0;
     .
     .
     .
    */

    // se parcurg toate submultimile
    for(int mask=0 ; mask < (1<<n) ; ++mask){

        // se parcurg toate nodurile
        for(int i=0;i<n;++i){

            // se verifica daca nodul curent se gaseste in submultimea curenta
            if(mask & (1<<i)){

                // se parcurg iarasi nodurile si se aplica recurenta
                for(int j=0;j<n;++j){

                    // ca sa nu fie probleme cu overflow verificam daca nodurile j si i sunt adiacente
                    // si daca exista un lant de la submultimea fara i care se termina in j
                    if(adq[j][i] != INT_MAX && maskMatrix[mask ^ (1<<i)][j] != INT_MAX )
                        maskMatrix[mask][i] = min(maskMatrix[mask][i], maskMatrix[mask ^ (1<<i)][j] + adq[j][i]);

                }

            }

        }

    }

    // cum am calculat toate lanturile hamiltoniene de cost minim
    // cautam ciclurile de cost minim
    int costMinim=INT_MAX;
    for(int i=0;i<n;++i)
        // testam daca exista ciclul si daca nodul de inceput 0 este adiacent cu nodul curent
        if(maskMatrix[(1<<n)-1][i] != INT_MAX && adq[i][0] !=INT_MAX)
            // calculam costul minim
            costMinim=min(costMinim,maskMatrix[(1<<n) - 1][i]+adq[i][0]);

    return costMinim;
}

int main() {
    fin >> n >> m;

    //matricea de adiacenta este si matricea de costuri
    adq.assign(n,vector<int>(n,INT_MAX));

    while(m--){
        int x,y,cost;
        fin>>x>>y>>cost;
        adq[x][y] = cost;
    }

    fout<<minCicluHamilton();
    return 0;
}

//5 10
//0 1 9
//0 3 8
//1 0 7
//1 2 1
//1 4 3
//2 0 5
//2 4 4
//3 2 6
//4 3 7
//4 1 1