#include <iostream>
#include <fstream>
#define bit(x) (1<<(x-1))
#include <vector>
#include <memory.h>
#include <climits>
#define MAX 20

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int a[MAX][MAX], dp[bit(19)][MAX], n, m, k;

int main()
{
    memset(dp, CHAR_MAX, sizeof(dp));
    int x, y;
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>k;
        a[++x][++y]=k;
    }
    dp[1][1]=0;
    for(int i=1; i<bit(n+1); i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(i&bit(j))
            {
                for(int x=1; x<=n; x++)
                    if((i & bit(x))==0 && a[j][x])
                        dp[i|bit(x)][x] = min(dp[i|bit(x)][x], dp[i][j]+a[j][x]);
            }

        }
    }
    int rez=INT_MAX;
    for(int i=1; i<=n; i++)
        if(a[i][1])
            rez=min(rez, dp[(bit(n+1))-1][i]+a[i][1]);
    g<<rez;

}