#include <iostream>
#include <fstream>
#include <vector>
#define oo 2000000000
using namespace std;
struct str
{
    int nod,cost;
};
vector <str> a[20];
int doi[20];
int dp[265000][20];
int n,m;
int suma,sol;
void Ini()
{
    int i,j;
    for(i=0; i<doi[n]; i++)
        for(j=0; j<n; j++)
        dp[i][j]=oo;

}
void Read()
{
    ifstream fin("hamilton.in");
    fin>>n>>m;
    int x;
    str w;
    Ini();
    for(int i=1; i<=m; i++)
    {
        fin>>x>>w.nod>>w.cost;
        a[x].push_back(w);
        dp[i<<x][w.nod]=w.cost;
    }

}
void Pdoi()
{

    doi[0]=1;
    for(int i=1; i<=n; i++)
        doi[i]=doi[i-1]*2;

    suma=doi[n]-1;

}

void Salv()
{
    int k,j,fiu,minim,i;
    for(i=0; i<doi[n]; i++)
        for(j=0; j<n; j++)
        if( ! ((i>>j) & 1) )
        for(k=0; k<a[j].size(); k++)
        if( !((i>>a[j][k].nod) & 1) )
    {
        fiu=a[j][k].nod;
        dp[i][j]=min(dp[i][j],dp[i^doi[j]][fiu]+a[j][k].cost);
    }

}
int main()
{

    Read();
    Pdoi();
    Salv();
    int i;
    sol=oo;
    for(i=0; i<a[0].size(); i++)
        sol=min(sol,dp[suma][a[0][i].nod]+a[0][i].cost);
        cout<<sol;
    return 0;
}