#include <iostream>
#include <vector>
#include <fstream>
#include <limits>

const int NMAX = 20, INF = std::numeric_limits<int>::max();
int n, m;

std::vector<int> vecini[NMAX], costuri[NMAX];
int viz[20], sol = INF;

void dfs(int nod, int nr, int cost)
{
    viz[nod] = 1;

    for(int i = 0; i < vecini[nod].size(); ++i)
    {
        if(!viz[vecini[nod][i]])
            dfs(vecini[nod][i], nr + 1, cost + costuri[nod][i]);
        if(nr == n && vecini[nod][i] == 0)
            sol = std::min(sol, cost + costuri[nod][i]);
    }

    viz[nod] = 0;
}

int main()
{
    std::ifstream in("hamilton.in");
    std::ofstream out("hamilton.out");
    int i, x, y, c;

    in >> n >> m;

    for(i = 1; i <= m; i++)
    {
        in >> x >> y >> c;
        vecini[x].push_back(y);
        costuri[x].push_back(c);
    }

    dfs(0, 1, 0);
    out << sol;

    return 0;
}