#include <iostream>
#include <fstream>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int a[50][50],v[100],x,y,c,n,m,i,j,s,mini=100001;
int suma(int n)
{
    int i,s=0;
    for(i=1;i<n;i++)
        s=s+a[v[i]][v[i+1]];
    s=s+a[v[n]][v[1]];
    return s;
}
bool verif(int i)
{
    int j;
    for(j=1;j<i;j++)
    {
        if(a[v[j]][v[j+1]]==0)
            return 0;
        if(v[j]==v[i])
            return 0;
    }
    return 1;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        a[x+1][y+1]=c;
    }

    i=1;
    while(i)
    {
        v[i]++;
        if(v[i]>n)
        {
            v[i]=0;
            i--;
        }
        else
        {
            if(verif(i))
            {
                if(i==n and a[v[n]][v[1]])
                {
                    s=suma(n);
                    if(mini>s)
                    {
                        mini=s;
                    }
                }
                else
                    i++;
            }
        }
    }
    g<<mini;
    return 0;
}