#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <numeric>
#include <cstring>
#include <string>
#include <queue>
#include <set>
#include <fstream>
#define pb push_back
#define mp make_pair
#define INF numeric_limits<int>::max()
#define bit(x) (-x)&x
#define int64 long long
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
int d[20][20],dp[1<<19][19],n;
void roy()
{
    for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    if(i!=j && d[i][k] && d[k][j] && (d[i][j]>d[i][k]+d[k][j] || !d[i][j]))
        d[i][j]=d[i][k]+d[k][j];
}
int main()
{
    int m;
    in>>n>>m;
    for(;m;m--)
    {
        int x,y,z;
        in>>x>>y>>z;
        d[x][y]=z;
    }
    roy();
    for(int k=0;k<(1<<n);k++)
    for(int i=0;i<n;i++)
        dp[k][i]=INF;
    for(int i=1;i<n;i++)
        dp[1<<i][i]=d[0][i];
    for(int k=0;k<(1<<n);k++)
    for(int i=0;i<n;i++)
    if(dp[k][i]!=INF)
    {
        for(int t=0;t<n;t++)
            if((k&(1<<t))==0 && dp[k|(1<<t)][t] > dp[k][i]+d[i][t])
                dp[k|(1<<t)][t]=dp[k][i]+d[i][t];
    }
    out<<dp[(1<<n)-1][0]<<'\n';
    return 0;
}