#include <fstream>
#include <fstream>
#include <map>
#include <vector>
#include<cmath>
#define nmax 19
#define inf 200000001
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

vector<vector<int>> l(nmax);
int dp[(1<<nmax)][nmax];
int cost[nmax][nmax];
int n, m, x, y, c;

int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cost[i][j]=inf;
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y>>c;
        l[x].push_back(y);
        l[y].push_back(x);
        cost[x][y]=c;
    }

    dp[1][0]=0;

    for(int conf=2; conf<(1<<n); conf++)
    {
        for(int i=0; i<n; i++)
        {
            if(conf&(1<<i))
            {
                int ant = conf^(1<<i);
                dp[conf][i]=inf;
                for(int j=0; j<n; j++)
                {
                    if(ant&(1<<j))
                    {
                        dp[conf][i]=min(dp[conf][i],dp[ant][j]+cost[i][j]);
                    }
                }
            }
        }
    }

    int sol=inf;
    for(int i=0; i<n; i++)
        sol=min(sol,dp[(1<<n)-1][i]+cost[0][i]);///plus muchia de la 0 la i
    cout<<sol;
}