#include <fstream>
#include <vector>
std::ifstream cin("hamilton.in");
std::ofstream cout("hamilton.out");
#define maxn 20
#define INF 100000000;
#define min(a,b) a<b?a:b
std::vector <int> G[maxn];
int cost[maxn][maxn], C[1<<maxn][maxn];
int N,M,minim=INF;

int main()
{
    int x,y;
    cin>>N>>M;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cost[i][j]=INF;
    for(;M--;){
        cin>>x>>y;
        G[y].push_back(x);
        cin>>cost[x][y];
    }
    for(int i=0;i<(1<<N);i++)
        for(int j=0;j<N;j++)
            C[i][j]=INF;
    C[1][0]=0;
    for(int i=0;i< (1<<N);i++)
        for(int j=0;j<N;j++)
            if(i&(1<<j))
                for(unsigned int k=0;k<G[j].size();k++)
                    if(i&(1<<G[j][k]))
                        C[i][j]=min(C[i][j], cost[ G[j][k] ] [j] + C[i ^ (1<<j)][G[j][k]]);

    for(unsigned int i=0;i<G[0].size();i++)
        minim=min(minim, C[(1<<N)-1][G[0][i]]+cost[G[0][i]][0]);

    cout<<minim;
}