#include <bits/stdc++.h>
using namespace std;

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

vector<vector<pair<int, int>>>Adjacency;
vector<vector<int>>pd;

int main() {
    int n, m;
    fin>>n>>m;
    Adjacency.resize(n);
    pd.resize(n);
    int nr_sub = 1<<n;
    for (int i=0; i<n; i++)
        pd[i].assign(nr_sub, 1e9);

    for (int i=1;i<=m;i++) {
        int x, y, c;
        fin>>x>>y>>c;
        Adjacency[x].push_back({y, c});
    }
    pd[0][1]=0;

    for (int s=1; s < nr_sub; s++)
        for (int i = 0; i<n;i++) {
            if ( s & (1<<i) )
                for (auto &j : Adjacency[i])
                    if ((s & (1<<j.first)) && pd[j.first][s^(1<<i)] + j.second < pd[i][s])
                        pd[i][s]=min( pd[i][s], pd[j.first][s^(1<<i)] + j.second);
        }

    int cost_min=1e9;
    for (auto &e : Adjacency[0])
        if (pd[e.first][nr_sub-1] < 1e9)
            cost_min=min(cost_min,pd[e.first][nr_sub-1]+e.second);

    fout<<cost_min<<'\n';


    return 0;
}