#include <iostream>
#include <fstream>
#include <climits>
#define bit(x) (1<<(x-1)) /// cause if we left shift with 1, we will not have 1 one the first position, we'll have it on second
#include <memory.h>

using namespace std;

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

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

int main()
{
    memset(dp, CHAR_MAX, sizeof(dp));
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x, y, cost;
        f>>x>>y>>cost;
        a[++x][++y]=cost;
    }
    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 k=1; k<=n; k++)
                    if((i&bit(k))==0 && a[j][k])
                        dp[i | bit(k)][k]=min(dp[i | bit(k)][k], dp[i][j]+a[j][k]);
    int answ=INT_MAX;
    for(int i=1; i<=n; i++)
        if(a[i][1] && dp[bit(n+1)-1][i]!=dp[0][0])
            answ=min(answ, dp[bit(n+1)-1][i]+a[i][1]);
    if(answ!=INT_MAX)
        g<<answ;
    else g<<"Nu exista solutii";

}