#define NMAX 18
#define NRMAX (1<<18)-1
#define INF 0x3f3f3f3f

#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

int n, m;
int x, y, c;
int cost[NMAX][NMAX];
int dp[NMAX][NRMAX];
int amcalculat[NMAX][NRMAX];

void init(){
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cost[i][j] = INF;
}

void citire(){
    f>>n>>m;
    init();
    for(int i=1; i<=m; i++){
        f>>x>>y>>c;
        cost[x][y] = c;
    }
}

int parcurg(int i, int j){

    int vmin = INF;
    if((1<<i) == j || i==0 && j==0)
        return 0;
    if(amcalculat[i][j] == 1)
        return dp[i][j];
    for(int x=0; x<n; x++){
        if(cost[x][i]!=INF && (j&(1<<x)) ){
            vmin = min(parcurg(x, j^(1<<i)) + cost[x][i], vmin);
        }
    }
    dp[i][j] = vmin;
    amcalculat[i][j] = 1;
    return dp[i][j];
}
int main()
{
    citire();
    int afis = INF;
    for(int v=0; v<n; v++)
        if(cost[v][0]!=INF)
            dp[v][(1<<n)-1] = parcurg(v, (1<<n)-1);

    for(int v=0; v<n; v++){
        if(cost[v][0]!=INF)
            afis = min(dp[v][(1<<n)-1] + cost[v][0], afis);
    }
    g<<afis;
    return 0;
}