#include <bits/stdc++.h>
#define oo 0x3f3f3f3f
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n, m, x, y, cost;
int ans;
vector<int> graf[25];
int Cost[25][25];
int C[262150][25];

void Read()
{
    ans = oo;
    f>>n>>m;
    for(int i = 0;i < n;++i)
        for(int j = 0;j < n;++j)
            Cost[i][j] = oo;
    for(int i = 1;i <= m;++i)
    {
        f>>x>>y;
        graf[y].push_back(x);
        f>>Cost[x][y];
    }
    memset(C, -1, sizeof(C));
    C[1][0] = 0;
}

int calc(int conf, int last)
{
    if(C[conf][last] == -1)
    {
        C[conf][last] = oo;

        for(vector<int>::iterator it = graf[last].begin();it != graf[last].end();++it)
            if(conf & (1 << *it))
            {
                if(*it == 0 && conf != (1 << last) + 1) continue;

                C[conf][last] = min(C[conf][last], calc(conf ^ (1 << last), *it) + Cost[*it][last]);
            }
    }
    return C[conf][last];
}

int main()
{
    Read();
    for(vector<int>::iterator it = graf[0].begin();it != graf[0].end();++it)
        ans = min(ans, calc((1 << n) - 1, *it) + Cost[*it][0]);
    g<<ans;
    return 0;
}