#include <fstream>
#include <vector>
#define DIM 18
#define INF 1e9
#define ff first
#define ss second

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n, m, dp[(1<<DIM) + 1][DIM], viz[(1<<DIM)][DIM], x, y, c, minim = INF;

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

bool test(int sub, int x){
    return !(sub & (1<<x));
}

int main()
{
    f>>n>>m;
    for(int i = 1; i <= m; ++ i){
        f>>x>>y>>c;
        graf[x].push_back(make_pair(y, c));
    }
    int kk = (1<<n) - 1;
    viz[1][0] = 1;
    for(int i = 1; i <= kk; ++ i)
        for(int j = 0; j < n; ++ j)
            for(int k = 0; k < graf[j].size(); ++ k){
                pair<int, int> nod = graf[j][k];
                if(test(i, nod.ff) && viz[i][j] == 1){
                    if(viz[i + (1<<nod.ff)][nod.ff])
                        dp[i + (1<<nod.ff)][nod.ff] = min(dp[i + (1<<nod.ff)][nod.ff], dp[i][j] + nod.ss);
                    else
                        dp[i + (1<<nod.ff)][nod.ff] = dp[i][j] + nod.ss;
                    viz[i + (1<<nod.ff)][nod.ff] = 1;
                }
            }

    for(int i = 0; i < n; ++ i)
        if(viz[kk][i])
            for(int j = 0; j < graf[i].size(); ++ i){
                if(graf[i][j].ff == 0)
                    minim = min(minim, dp[kk][i] + graf[i][j].ss);
            }
    g<<minim;
    return 0;
}