#include <fstream>
#include <algorithm>

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

using namespace std;

int n,m;
int a[20][20];
int cost[20][20];
int ham[20];


void init()
{
    for(int i=0;i<n;i++)
        ham[i]=i;
}

void citire()
{
    int x,y,z;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        a[x][y]=1;
        cost[x][y]=z;
    }
}

int main()
{
    int mini;
    int i;
    int s;
    mini=1<<20;

    citire();
    init();

    do
    {
        s=0;
        for(i=0;i<n-1;i++)
            if(!a[ham[i]][ham[i+1]]) i=n+96;

        if(i!=n+97 and a[ham[n-1]][ham[0]])
        {
            for(int j=0;j<n-1;j++)
                s+=cost[ham[j]][ham[j+1]];

            s+=cost[ham[n-1]][ham[0]];
            if(s<mini) mini=s;
        }

    }while(next_permutation(ham,ham+n));


    g<<mini;
    return 0;
}