#include <fstream>
#include <vector>
#include <cstdlib>
#define INF 900000000
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,x,y,i,j,k,cmin,Cost[20][20],C[(1<<18)+5][19];
vector<int> A[20];
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            Cost[i][j]=INF;

    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        A[y].push_back(x);
        fin>>Cost[x][y];
    }

    for(int i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
            C[i][j]=INF;
    C[1][0]=0;

    for(int j=1;j<(1<<n);j++)
        for(int k=1;k<n;k++)
            if(j&(1<<k))
                for(int i=0;i<A[k].size();i++)
                    if(j&(1<<A[k][i]))
                    {
                        C[j][k]=min(C[j][k],C[j^(1<<k)][A[k][i]]+Cost[A[k][i]][k]);
                    }
    cmin=INF;
    for(int i=0;i<A[0].size();i++)
        cmin=min(cmin,C[(1<<n)-1][A[0][i]]+Cost[A[0][i]][0]);
    fout<<cmin<<'\n';
    return 0;
}