//brut

#include <bits/stdc++.h>
#define Nmax 25
#define DIM 700000
using namespace std;
class Ifstream
{
private:
    FILE *f;
    char *buffer;
    int cursor;
    char read_ch()
    {
        if(++cursor==DIM)
        {
            cursor=0;
            fread(buffer,1,DIM,f);
        }
        return buffer[cursor];
    }
public:
    Ifstream (const char *file_name)
    {
        f=fopen(file_name,"r");
        cursor=0;
        buffer=new char[DIM]();
    }
    Ifstream &operator >> (int &n)
    {
        char c;
        n=0;
        while(!isdigit(c=read_ch()));
        n=c-'0';
        while(isdigit(c=read_ch()))
            n=n*10+c-'0';
        return *this;
    }
};
Ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m;
int a[Nmax][Nmax];
list <int> G[Nmax];
int sol[Nmax];
int ans,best=INT_MAX;
bool viz[Nmax];
void bkt(int k)
{
    for(const auto &it:G[sol[k-1]])
        if(!viz[it])
        {
            viz[it]=true;
            ans+=a[sol[k-1]][it];
            sol[k]=it;
            if(k==n)
            {
                if(a[sol[n]][sol[1]]) best=min(ans+a[sol[n]][sol[1]],best);
            }
            else bkt(k+1);
            ans-=a[sol[k-1]][it];
            viz[it]=false;
        }
}
int main()
{
    f>>n>>m;
    int i,j,k;
    while(m--)
    {
        f>>i>>j>>k;
        G[i+1].push_back(j+1);
        a[i+1][j+1]=k;
    }
    for(i=1;i<=n;i++)
        G[0].push_back(i);
    bkt(1);
    g<<best;

    return 0;
}