#include <fstream>
using namespace std;
ifstream f ("hamilton.in");
ofstream g ("hamilton.out");
struct
{
    int a,b,c;
}v[20*20];
int n,m,d[1<<18][20],sol;
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>v[i].a>>v[i].b>>v[i].c;
    }
    for(int i=0;i<(1<<n);++i)
    {
        for(int j=0;j<n;++j) d[i][j]=2e9;
    }
    d[1][0]=0;
    for(int i=0;i<(1<<n);++i)
    {
        for(int j=1;j<=m;++j)
        {
            if((i&(1<<v[j].a))&&(i&(1<<v[j].b)))
            {
                d[i][v[j].b]=min(d[i][v[j].b],d[i^(1<<v[j].b)][v[j].a]+v[j].c);
            }
        }
    }
    sol=2e9;
    for(int i=0;i<n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(v[j].a==i&&v[j].b==0) sol=min(sol,d[(1<<n)-1][i]+v[j].c);
        }
    }
    g<<sol;
    return 0;
}