#include <fstream>
#include <vector>
#define LONG_LONG_MAX 980000000
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
struct muchie {int y;long long int cost;};
vector <muchie> g[19];
long long int v[524888];
int n,m,a,b,c;
void dp(int masc,int x);
int main()
{
    int i,masc=0;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        g[a].push_back({b,c});
    }
    int rez=1<<n;
    for(i=1;i<=rez;i++)
        v[i]=LONG_LONG_MAX;
    v[0]=0;
    dp(masc,0);
    fout<<v[(1<<n)-1];
    return 0;
}
void dp(int masc,int x)
{
    int i;
    for(i=0;i<g[x].size();i++)
    {
        if((masc&(1<<g[x][i].y))==0)
        {
            v[(masc^(1<<g[x][i].y))]=min(v[(masc^(1<<g[x][i].y))],v[masc]+g[x][i].cost);
            dp((masc^(1<<g[x][i].y)),g[x][i].y);
        }
    }
}