#include <fstream>

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m;
int d[(1<<20)][20],x,y,z,a[20][20];
int main()
{
    f>>n>>m;
    n--;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        a[x][y]=z;
    }
    int lg=(1<<(n+1));
    for(int i=0;i<=lg;i++)
        for(int j=0;j<=n;j++)
            d[i][j]=1e9;
    d[0][0]=d[1][0]=0;
    for(int i=1;i<lg;i++)
    {
        for(int j=0;j<=n;j++)
            if((1<<j)&i)
                for(int t=0;t<=n;t++)
                    if(!(i&(1<<t))&&a[j][t])
                        d[i^(1<<t)][t]=min(d[i^(1<<t)][t],d[i][j]+a[j][t]);
    }
    int mn=1e9;
    for(int i=0;i<n;i++)
        if(a[i][0])
            mn=min(mn,d[lg-1][i]+a[i][0]);
    g<<mn;
    return 0;
}