#include <bits/stdc++.h>

using namespace std;

#define NMAX 18
vector<vector<pair<int, int>>> graph(NMAX);
int n, m;

void readFromFile(){
    ifstream fin("hamilton.in");
    fin>>n>>m;

    int x, y, c;
    for(int i=1; i<=m; i++){
        fin>>x>>y>>c;
        graph.at(x).push_back(make_pair(y, c));
    }
    fin.close();

}

vector<bool> visited(NMAX);
int sol = (1<<30)-1;

void DFS(int nod, int nr, int cost){
    visited.at(nod)=true;


    for(auto& elem:graph.at(nod)){
        if(!visited.at(elem.first)) DFS(elem.first, nr+1, cost+elem.second);
        if(nr==n && elem.first==0) sol = min(sol, cost+elem.second);
    }
    visited.at(nod) = false;
}

int main()
{
    readFromFile();
    DFS(0, 1, 0);
    ofstream fout("hamilton.out");
    fout<<sol;
    fout.close();
}