#include <fstream>
#include <vector>
#include <iostream>
#include <cstring>
#define DIM 20
#define MAX (1<<20)
#define INF 2000000000
using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int N,M;

vector <pair <int,int> > L[DIM];

int D[MAX][DIM];

int Sol,V[DIM];

int main(){

    fin >> N >> M;

    while(M--){
        int x,y,c;
        fin >> x >> y >> c;
        L[x].push_back(make_pair(y,c));
        if(y==0){
            V[x]=c;
        }
    }

    int mask = (1<<N)-1;

    for(int i=0;i<=mask;i++)
        for(int j=0;j<N;j++)
            D[i][j] = INF;

    D[1][0]=0;
    for(int i=1;i<=mask;i++)
        for(int j=0;j<N;j++)
            if((i&(1<<j))){
                if(D[i][j]!=INF)
                for(int x=0;x<L[j].size();x++){
                        int vecin = L[j][x].first;
                        int cost = L[j][x].second;
                        int nextStare = i + (1<<vecin);
                        if(((i&(1<<vecin))==0) && D[nextStare][vecin] > D[i][j] + cost)
                                D[nextStare][vecin] = D[i][j] + cost;
                }
            }

    Sol = 0x3f3f3f3f;

    for(int i=0;i<N;i++)
        if(V[i])
            Sol=min(Sol,D[mask][i]+V[i]);

    fout << Sol << "\n" ;

}