#include <iostream>
#include <fstream>

using namespace std;

//int minim = 0x7fffffff; // +oo
    /*  0x    7    f    f    f    f    f    f    f
    binary 0111 1111 1111 1111 1111 1111 1111 1111 */

//int p;
int mem[18][1<<18];

class Graf {
public:
    int n,m,mat[18][18];

    Graf()
    {
        int i,j;
        n=0; m=0;
        for(i=0;i<18;++i)
            for(j=0;j<18;++j)
            {
                mat[i][j]=0;
            }
    }

    int hamilton(int nod, int nr, int vizitati)
    {
        int i, minim, k;
        if (mem[nod][vizitati] == 0)
        {
            //++p;
            if (nr == n) {
                if(mat[nod][0] != 0) {
                    mem[nod][vizitati] = mat[nod][0];
                } else {
                    mem[nod][vizitati] = 0x3fffffff;
                }
            } else {
                minim = 0x3fffffff;
                for (i = 1; i < n; ++i) {
                    if (mat[nod][i] != 0 && (vizitati & (1 << i)) == 0) {
                        k = hamilton(i, nr + 1, vizitati ^ (1 << i));
                        if (minim > mat[nod][i] + k)
                            minim = mat[nod][i] + k;
                    }
                }
                //cout << nod << " " << nr << " " << vizitati << " " << minim << "\n";
                mem[nod][vizitati] = minim;
            }
        }
        return mem[nod][vizitati];
    }
};

int main(void) {
    ifstream in("hamilton.in");
    ofstream out("hamilton.out");
    int i, x, y;
    Graf g;
    in >> g.n >> g.m;
    for(i = 1; i <= g.m; ++i)
    {
        in >> x >> y;
        in >> g.mat[x][y];
    }
    out << g.hamilton(0,1,1);
    //cout << "\n" << p;
    return 0;
}