#include <bits/stdc++.h>
#define oo 1e9
#define NOD 19
#define BITS (1<<NOD)

using namespace std;

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

int dp[BITS][NOD],cost[NOD][NOD],n,m;
int x,y,c;
//dp[i][j]-costul minim al unui ciclu hamiltonian care se termina in nodul i si contine nodurile bits.

inline void Read()
{
    fin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cost[i][j]=oo;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        cost[x][y]=c;
    }
}

inline void DP_Solve()
{
    int valmax=(1<<n)-1;
    for(int i=0;i<n;i++)
        for(int j=0;j<=valmax;j++)
                dp[j][i]=oo;
    dp[1][0]=0;
    for(int stare=1; stare<=valmax; stare++)
        for(int i=0;i<n;i++)
            if((stare&(1<<i))) // daca 'stare' contine in reprezentarea sa binara  nodul i =  primul -> ultimul
            {
                for(int j=0;j<n;j++)
                    if(!(stare&(1<<j)) && cost[i][j])//exista muchie i->j si nu am trecut prin nodul j(starea)
                        dp[stare|(1<<j)][j]=min(dp[stare|(1<<j)][j],dp[stare][i]+cost[i][j]);
            }
    int costfinal=oo;
    for(int i=0;i<n;i++)
        costfinal=min(costfinal,dp[valmax][i]+cost[i][0]);//adaugam si muchia i->0
    if(costfinal==oo)
         fout<<"Nu exista solutie\n";
    else fout<<costfinal<<"\n";
}
int main()
{
    Read();
    DP_Solve();

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