#include <bits/stdc++.h>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n, x, y, i, v[25], a[25][25], minn = INT_MAX, s, m, c;
void write()
{
    s = 0;
    for(int i = 1;i < n;i++)
        s = s + a[v[i]][v[i + 1]];
    s = s + a[v[n]][v[1]];
    if(s < minn)minn = s;
}
bool valid(int k)
{
    if(k == n && a[v[k]][v[1]] == 0)return false;
    if(k > 1 && a[v[k - 1]][v[k]] == 0)return false;
    for(int i = 1;i < k;i++)
        if(v[i] == v[k])return false;
    return true;
}
void back(int k)
{
    for(int i = 1;i <= n;i++)
    {
        v[k] = i;
        if(valid(k))
        {
            if(k == n)write();
            else back(k + 1);
        }
    }
}
int main()
{
    f >> n >> m;
    for(i = 1;i <= m;i++)
    {
        f >> x >> y >> c;
        x++;
        y++;
        a[x][y] = c;
    }
    back(1);
    if(minn != INT_MAX)g << minn;
    else g << "0";
    return 0;
}