#include <bits/stdc++.h>
#define Dmax 20
#define inf 0x3F3F3F3F
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m,Cost[Dmax][Dmax],C[262150][Dmax];

int main()
{
    f>>n>>m;
    for(int i = 0; i < n; i++)  ///     ADAUGAM COSTUL DINTRE TOATE NODURILE == INFINIT
        for(int j = 0; j< n; j++)
        Cost[i][j] = inf;
    for(int i = 1; i <= m; i++)
    {
        int x,y,z;                  ///CITIM DISTANTELE CUNOSCUTE INTRE NODURI IN MATRICEA COST
        f>>x>>y>>z;
        Cost[x][y] = z;
    }
    int lim = 1<<n;                     ///ADAUGAM LIMITA MASTII = 1 URMAT DE N ZEROURI(PT A INCAPEA TOATE)
    for(int i = 1; i< lim; i++)         /// SETAM DRUMURILE INTRE NODURI CARE TREC PRIN MASK NODURI CU INF
        for(int j = 0; j < n; j++)
        C[i][j] = inf;
    C[1][0] = 0;                        /// DRUMUL DE LA 0 PANA LA 0 CE CONTINE UN NOD(0) = 0;
    for(int mask = 1; mask < lim; mask++)  ///PARCURGEM TOATE MASTILE( LA FINAL VOR FI 111..1(N-1) - TOATE ND
        for(int i = 0; i < n; i++)         ///PARCURGEM TOATE NODURILE
            if((mask & (1<<i))&&(C[mask][i]!=inf)) ///VERIFICAM DACA NODUL E IN MASCA SI E DIST PANA LA NOD
                for(int j = 0; j < n; j++) /// CAUTAM VECINI
                    if(!(mask & (1<<j))&&(Cost[i][j]!=inf)) ///VERIFICAM SA NU FIE IN MASCA SI SA FIE DIST
                {
                        int newMask = mask|(1<<j);   ///FACEM NOUA MASKA
                        C[newMask][j] = min(C[newMask][j],C[mask][i]+ Cost[i][j]);  ///ACTUALIZAM COSTUL
                }
    int sol = inf;
    for(int i = 1; i < n;i++)
        sol = min(sol,C[(1<<n)-1][i]+ Cost[i][0]); ///ADAUGAM 0 IARASI PT A OBTINE UN CICLU
        g<<sol;    ///IN min(C[(1<<n)-1][i]) - drum hamiltonian de cost minim;


    return 0;
}