#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int d[263000][18],n,m;
int a[19][19];

void initializare()
{
    for(int i=0;i<18;i++)
        for(int j=0;j<18;j++)
            a[i][j]=19000000;
    for(int i=0;i<=263000;i++)
        for(int j=0;j<=18;j++)
            d[i][j]=19000000;
}

void citire()
{
    scanf("%d %d",&n,&m);
    int x,y,z;
    for(int i=0;i<m;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        a[x][y]=z;
    }
}


int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    initializare();
    citire();

    d[1][0]=0;

    for(int j=3;j<(1<<n);j+=2)
        for(int k=1;k<n;k++)
            for(int v=0;v<n;v++)
                d[j][k]=min(d[j][k],d[j^(1<<k)][v]+a[v][k]);

    for(int k=1;k<n;k++)
        d[(1<<n)-1][0]=min(d[(1<<n)-1][0],d[(1<<n)-1][k]+a[k][0]);

    printf("%d",d[(1<<n)-1][0]);
    return 0;
}