#include <bits/stdc++.h>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int oo=2e9;

int n,m;
int cost[20][20];
int dp[(1<<18)+5][20];

void Build()
{
    int Smax;
    Smax=(1<<n)-1;

    for(int stare=0;stare<=Smax;stare++)
        for(int i=0;i<n;i++)
            dp[stare][i]=oo;

    dp[1][0]=0;

    for(int stare=1;stare<=Smax;stare++)
        for(int i=0;i<n;i++)
            if(dp[stare][i]!=oo)
                for(int j=0;j<n;j++)
                    if(cost[i][j] && !((1<<j) & stare))
                        dp[(1<<j) + stare][j] = min(dp[(1<<j) + stare][j], dp[stare][i]+cost[i][j]);

    int sol=oo;

    for(int i=1;i<n;i++)
        if(cost[i][0])
            sol=min(sol,dp[Smax][i]+cost[i][0]);

    if(sol==oo)fout<<"Nu exista solutie";
    else fout<<sol<<"\n";
}


int main()
{
    fin>>n>>m;

    int x,y,c;
    while(m--)
    {
        fin>>x>>y>>c;
        cost[x][y]=c;
    }

    Build();

    fin.close();
    fout.close();
    return 0;
}