// back-20p
#include <iostream>
#include <fstream>
#include <vector>
#define Nmax 100005
#define INF 0x3f3f3f3f

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n, m;
int a[20][20];
// vector <pair <int, int> > v[Nmax];
// int dp[(1<<18)][18]; // am parcurs nodurile din reprez binara a lui i si suntem in j

bool used[20];
int p[20];
int ans=INF;

void afis()
{
    for (int i = 1; i <= n; i++)
    {
        cout << p[i] << " ";
    }
    cout << '\n';
}

int verif()
{
    int ans=0;
    for (int i = 1; i < n; i++)
    {
        if (a[p[i]][p[i+1]] == 0) return -1;
        else
        {
            ans+=a[p[i]][p[i+1]];
        }
    }
    if (a[p[n]][p[1]] == 0) return -1;
    else ans+=a[p[n]][p[1]];
    return ans;
}

void bkt(int niv)
{
    if (niv == n+1)
    {
        //afis();
        int x=verif();
        if (x != -1)
        {
            if (ans > x)
            {
                ans=x;
                //afis();
            }
        }
    }
    else
    {
        for (int i = 1; i <= n; i++)
            if (!used[i])
            {
                used[i]=1;
                p[niv]=i;
                bkt(niv+1);
                used[i]=0;
            }
    }
}

int main()
{
    f >> n >> m;

    for (int i = 1, x, y, c; i <= m; i++)
    {
        f >> x >> y >> c;
        x++, y++;
        //cout << x << "  " <<  y << " " << c << '\n';
        a[x][y]=c;
    }
    bkt(1);
    g << ans;

    return 0;
}