#include <fstream>

using namespace std;

ifstream fi("hamilton.in");
ofstream fo("hamilton.in");

const int inf = 1e9;

bool check_if_1(int msk, int bit) {
    return (msk & (1 << bit)) != 0;
}

int add_to_msk(int msk, int bit) {
    return msk | (1 << bit);
}

int Cost[20][20];
int Dp[1 << 18][20];

int main() {
    int N, M;
    fi >> N >> M;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            Cost[i][j] = inf;
        }
    }

    for (int msk = 0; msk < (1 << 18); msk++) {
        for (int i = 0; i < N; i++) {
            Dp[msk][i] = inf;
        }
    }

    for (int i = 0; i < M; i++) {
        int x, y, c;
        fi >> x >> y >> c;

        Cost[x][y] = c;
    }

    Dp[1][0] = 0;
    for (int msk = 0; msk < (1 << 18); msk++) {
        for (int nod1 = 0; nod1 < N; nod1++) {
            if (!check_if_1(msk, nod1)) {
                continue;
            }

            for (int nod2 = 0; nod2 < N; nod2++) {
                if (check_if_1(msk, nod2) || nod1 == nod2) {
                    continue;
                }

                int msk_new = add_to_msk(msk, nod2);
                Dp[msk_new][nod2] = min(Dp[msk_new][nod2], Dp[msk][nod1] + Cost[nod1][nod2]);
            }
        }
    }

    int rez = inf;
    for (int nod = 0; nod < N; nod++) {
        rez = min(rez, Dp[(1 << N) - 1][nod] + Cost[nod][0]);
    }

    if (rez == inf) {
        fo << "Nu exista solutie";
    }
    else {
        fo << rez << "\n";
    }
}