#include <fstream>
#include <vector>

using namespace std;
ifstream cin ("hamilton.in");
ofstream cout ("hamilton.out");

int n, m, solution = 1e9, dp[262144][19];
vector <pair <int, int> > v[19];
void sol(int conf, int cost, int last)
{
    if(last == 1 && conf != 0 && conf != (1 << n) - 1)
        return;

    dp[conf][last] = min(dp[conf][last], cost);

    if(conf == (1 << n) - 1)
    {
        solution = min(solution, cost);
        return;
    }

    for(auto it = v[last].begin(); it != v[last].end(); ++it)
    {
        if(((conf >> (it->first)) & 1) == 0)
        {
            sol(conf ^ (1 << (it->first)), cost + it->second, it->first);
        }
    }
}
int main()
{
    cin >> n >> m;

    for(int i = 0; i <= (1 << n) - 1; ++i)
        for(int j = 1; j <= n; ++j)
        {
            dp[i][j] = 1e9;
        }

    for(int i = 1; i <= m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
    }

    sol((unsigned int)0, 0, 1);
    cout << solution << '\n';
    return 0;
}