#include <bits/stdc++.h>

using namespace std;
const int inf=1e9;
int cost[20][20]; ///cost[A][B] = costul de la A la B
int dp[1<<18][20]; ///dp[masca][Nod] = costul minim pt drumul ce trece doar prin nodurile din masca si se termina in nodul Nod
int main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    int noduri, muchii, a,b, c;
    cin>>noduri>>muchii;
    for(int i=0; i<noduri; i++)
        for(int j=0; j<noduri; j++)
            cost[i][j]=inf;
    for(int i=0; i<(1<<18); i++)
        for(int j=0; j<noduri; j++)
            dp[i][j]=inf;
    for(int i=1; i<=muchii; i++)
    {
        cin>>a>>b>>c;
        cost[a][b]=c;
    }
    ///deoarece ne intereseaza doar ciclurile, acestea pot incepe din orice nod dintr-o masca data deoarece drumul e circular si ne intoarcem de unde am plecat
    dp[1][0]=0; ///drumul ce contine doar nodul 0 are cost 0
    for(int masca=0; masca<(1<<18); masca++)
    {
        for(int nod1=0; nod1<noduri; nod1++)
        {
            if (!masca&(1<<nod1)) ///daca nod1 nu e in masca
                continue;
            for(int nod2=0; nod2<noduri; nod2++)
            {
                if (masca&(1<<nod2) || nod1 == nod2) ///daca nod2 e deja in masca
                    continue;
                int masca_noua = masca|(1<<nod2); ///bagam nod 2 in masca
                dp[masca_noua][nod2]=min(dp[masca][nod1]+cost[nod1][nod2], dp[masca_noua][nod2]);
            }
        }
    }
    int minn=inf;
    for(int nod_final=0; nod_final<noduri; nod_final++)
        minn=min(minn, dp[(1<<noduri)-1][nod_final]+cost[nod_final][0]);
    if(minn==inf)
        cout<<"Nu exista solutie";
    else
        cout<<minn;
    return 0;
}