#include <fstream>
#define NMAX 20
#define INF 200000000
using namespace std;

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

int n, m;
int C[NMAX][NMAX];
int sol[NMAX], solmin[NMAX];
int cost, costMin = INF;
int uz[NMAX];

void init();
void BKT(int);

int main(){
    init();
    sol[1] = 1;
    uz[1] = 1;
    BKT(2);
    if(costMin == INF){
        fout<<"Nu exista solutie\n";
        return 0;
    }
    fout<<costMin<<'\n';

    return 0;
}

void init(){
    fin>>n>>m;
    int i, j;
    for(i = 1; i<= n; ++i)
        for(j = 1; j<= n; ++j) C[i][j] = INF;
    for(i = 1; i<=n; ++i) C[i][i] = 0;

    int x, y;
    for(i = 1; i<=m; ++i){
        fin>>x>>y; ++x; ++y;
        fin>>C[x][y];
    }
}

void BKT(int k){
    if(k == n+1){
        if(cost + C[ sol[n] ][sol[1]]  < costMin){
            int i;
            costMin = cost + C[ sol[n] ][sol[1]];
            for(i = 1; i<=n; ++i) solmin[i] = sol[i];
        }
        return;
    }
    int i;
    for(i = 1; i <= n; ++i){
        if(C[ sol[k-1] ][i] < INF && !uz[i]){
            uz[i] = 1;
            sol[k] = i;
            cost += C[sol[k-1]][i];
            BKT(k+1);
            uz[i] = 0;
            cost -= C[sol[k-1]][i];
        }
    }
}