#include <fstream>

using namespace std;

int n;
int m;
int n2;
const int maxN = 18;
const int maxN2 = 1 << 18;
const int infinite = 100000000;
int matrix[maxN][maxN];

int incomming[maxN][maxN];
int incommingLength[maxN];

int memoValue[maxN2][maxN];

const int compute(const int bitPos,const int pos)
{
    if (memoValue[bitPos][pos] < 0)
    {
        memoValue[bitPos][pos] = infinite;

        for (int a = 0;a < incommingLength[pos];a += 1)
        {
            const int incommingPos = incomming[pos][a];
            if ((bitPos & (1 << incommingPos)) == 0)
            {
                continue;
            }
            if ((incommingPos == 0) && (bitPos != ((1 << pos) | 1)))
            {
                continue;
            }

            const int attempt = compute(bitPos & (~(1 << pos)),incommingPos) + matrix[incommingPos][pos];
            if (attempt < memoValue[bitPos][pos])
            {
                memoValue[bitPos][pos] = attempt;
            }
        }
    }
    return memoValue[bitPos][pos];
}

int main(void)
{
    fstream fin("hamilton.in",ios::in);
    fstream fout("hamilton.out",ios::out);

    fin >> n >> m;
    n2 = (1 << n);

    for (int a = 0;a < n2;a += 1)
    {
        for (int b = 0;b < n;b += 1)
        {
            memoValue[a][b] = -1;
        }
    }

    for (int a = 0;a < n;a += 1)
    {
        for (int b = 0;b < n;b += 1)
        {
            matrix[a][b] = infinite;
        }
    }

    for (int a = 0;a < n;a += 1)
    {
        incommingLength[a] = 0;
    }

    for (int a = 0;a < m;a += 1)
    {
        int x;
        int y;
        int c;
        fin >> x >> y >> c;
        matrix[x][y] = c;

        incomming[y][incommingLength[y]] = x;
        incommingLength[y] += 1;
    }

    memoValue[1][0] = 0;

    int best = infinite;
    for (int a = 0;a < incommingLength[0];a += 1)
    {
        int attempt = compute((1 << n) - 1,incomming[0][a]) + matrix[incomming[0][a]][0];
        if (attempt < best)
        {
            best = attempt;
        }
    }

    if (best == infinite)
    {
        fout << "Nu exista solutie\n";
    }
    else
    {
        fout << best << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}