#include <fstream>
#include <vector>
#define inf 1000004*18

using namespace std;

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

int n, m, a, b, c, i, j, vecin, cost, stare, d[262150][19], sol = inf;
vector<pair<int, int> > v[19];
char ok[19];

int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        v[a].push_back(make_pair(b, c));
        if(b == 0)
            ok[a] = c;
    }
    /// stare = ce noduri au fost folosite pana la un moment dat
    a = (1<<n)-1;
    for(stare = 1;stare <= a; stare += 2)
        for(i=0;i<n;i++)
            d[stare][i] = inf;
    d[1][0] = 0;
    for(stare = 1;stare <= a; stare += 2)
        for(i=0;i<n;i++){
            b = (1<<i);
            if((stare & b) != 0)
                for(j=0;j<v[i].size();j++){
                    vecin = v[i][j].first;
                    cost = v[i][j].second;
                    c = (1<<vecin);
                    if((stare & c) == 0)
                        d[stare+c][vecin] = min(d[stare+c][vecin], d[stare][i] + cost);
                }
        }
    for(i=1;i<n;i++)
        if(ok[i] != 0)
            sol = min(sol, d[a][i] +ok[i] );
    fout<<sol;
    return 0;
}