#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

#define INF 0x3f3f3f3f
#define Nmax 20

using namespace std;
int N, M;
vector<pair<int,int> > G[Nmax];
int DP[1<<18][Nmax]; /// DP[i][j] -> costul de a trece prin masca j si a termina pe nodul i

void read()
{
    scanf("%d%d",&N,&M);
    int a,b,c;
    for(int i = 1; i <= M; ++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        G[a].push_back(make_pair(c,b));
    }
}

void solve()
{
    memset(DP,INF,sizeof(DP));
    DP[1][0] = 0;
    for(int mask = 0; mask < ( 1<<N ); ++mask) /// luam toate configuratiile
        for(int j = 0; j < N; ++j)
            if(mask &(1<<j)) /// daca exista nodul j in masca
            for(vector<pair<int,int> >::iterator it = G[j].begin(); it != G[j].end(); ++it)
                if(mask & (1 << (it->second) )) /// si exista si nodul *it presupunem ca venim de acolo
                    DP[mask][j] = min(DP[mask][j], DP[mask^(1<<j)][it->second] + it->first);
    int ans = INF;
    for(vector<pair<int,int> >::iterator it = G[0].begin(); it != G[0].end(); ++it)
        ans = min(ans, DP[(1<<N)-1][it->second] + it->first);
    printf("%d\n",ans);
}

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    read();
    solve();

    return 0;
}