#include <cstring>
#include <fstream>
#include <vector>

using namespace std;

const int MAXN = 20;
const int MAXCONF = (1 << 18) + 1;
const int INF = 1e9;

int N, M, cost_ham;
vector<int> pred[MAXN];
int Cost[MAXN][MAXN];
int cd[MAXCONF][MAXN];

int cost_drum(int conf, int ultim) {
    if (cd[conf][ultim] == -1) { // Trebuie calculat.
        cd[conf][ultim] = INF;   // Initializam un minim.
        for (int nod : pred[ultim])
            if (conf & (1 << nod))  // nod se afla in configuratie
                if (nod != 0 or ((conf ^ (1 << ultim)) == 1)) {
                    int cost_nod = cost_drum(conf ^ (1 << ultim), nod);
                    if (cd[conf][ultim] > cost_nod + Cost[nod][ultim])
                        cd[conf][ultim] = cost_nod + Cost[nod][ultim];
                }
    }
    return cd[conf][ultim];
}


int main() {
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    fin >> N >> M;
    memset(Cost, 127, sizeof(Cost)); // 2.139.062.143
    for (int i = 1; i <= M; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        pred[y].push_back(x); // arcul invers
        Cost[x][y] = c;
    }
    cost_ham = INF;
    memset(cd, -1, sizeof(cd));
    cd[1][0] = 0;
    for (int nod : pred[0]) {
        int cost_vecin = cost_drum((1 << N) - 1, nod);
        if (cost_ham > cost_vecin + Cost[nod][0])
            cost_ham = cost_vecin + Cost[nod][0];
    }
    if (cost_ham != INF)
        fout << cost_ham << '\n';
    else
        fout << "Nu exista solutie" << '\n';
    return 0;
}    
    /*
 
 
10000
 1111

    3210
    1110
    1000
    ----
    0110
    

    15
        14
            12
                8
            12
                4
        14
            10
                8
            10
                2
        14
            6
                4
            6
                2
    15
        13
            12
                8
            12
                4
        13
            9
                8
            9
                1
        13
            5
                4
            5
                1
    15
        11
            10
                8
            10
                2
        11
            9
                8
            9
                1
        11
            3
                2
            3
                1
    15
        7
            6
                4
            6
                2
        7
            5
                4
            5
                1
        7
            3
                2
            3
                1


    11010111 ^
    01000000
    --------
    10010111

    */