#include <fstream>
#include <vector>
using namespace std;

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

using VVI = vector<vector<int> >;

const int inf = 0x3f3f3f3f;
VVI G;
int w[19][19], n, m, ham[1 << 18][19];

void ReadFunction();

int main()
{
    ReadFunction();

    for (int mask = 0; mask < (1 << n); ++mask)
        for (int i = 0; i < n; ++i)
            ham[mask][i] = inf;
    ham[1][0] = 0;
    for (int i = 0; i < (1 << n); ++i)
        for (int j = 0; j < n; ++j)
            if (i & (1 << j))
                for (const auto& k : G[j])
                    if (!(i & (1 << k)))
                        ham[i | (1 << k)][k] = min(ham[i | (1 << k)][k], ham[i][j] + w[j][k]);

    int res = inf;
    for (int i = 0; i < n; ++i)
        res = min(res, ham[(1 << n) - 1][i] + w[i][0]);
    fout << res;
}

void ReadFunction()
{
    fin >> n >> m;

    G = VVI(n + 1);

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            w[i][j] = inf;

    for (int i = 1, x, y, z; i <=m; ++i)
    {
        fin >> x >> y >> z;
        G[x].push_back(y);
        w[x][y] = z;
    }
}