#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector <int> G[20];
vector <int> ::iterator IT;
int dp[(1<<18)+2][20],m,n;
int costuri[20][20];
void citire()
{
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            costuri[i][j]=0x3f3f3f3f;

    int aux1,aux2,cost;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d",&aux1,&aux2,&cost);
        G[aux2].push_back(aux1);
        costuri[aux1][aux2]=cost;
    }
}
void solve()
{
    int rasp=0x3f3f3f3f;
    for(int i=0; i<(1<<n); i++)
        for(int j=0; j<n; j++)
            dp[i][j]=0x3f3f3f3f;

    dp[1][0]=0;
    for(int i=1; i<(1<<n); i++)
        for(int j=0; j<n; j++)
            if(i&(1<<j))
            {
                for(IT=G[j].begin(); IT!=G[j].end(); IT++)
                {

                    if(i&(1<<*IT))
                        dp[i][j]=min(dp[i^(1<<j)][*IT]+costuri[*IT][j],dp[i][j]);
                }
            }

    for(IT=G[0].begin(); IT!=G[0].end(); IT++)
        rasp=min(rasp,dp[(1<<n)-1][*IT]+costuri[*IT][0]);

    if(rasp==0x3f3f3f3f)
        printf("Nu exista solutie");
    else
        printf("%d",rasp);
}
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    citire();
    solve();
    return 0;
}