/// Problema NP completa
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

#define inf 2e9  /// = 2 * 10^9
int n, m;
vector <pair <int, int>> G[20];

/// dp[i][j] = costul minim sa ajung in j trecand prin nodurile care sunt
/// bitii de 1 ai lui i in binar  (i repr un drum in graf, pentru a verifica daca nodul k
/// este in acel drum facem i&(1<<k), daca rez e 0 => k nu e prin nodurile lui i, else k e printre nodurile lui i)
int dp[1<<18][18];

int main()
{
    int x, y, cost, newi;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>cost;
        G[y].push_back({x, cost}); /// G[i] = muchiile care 'intra' in i (celalalt capat si costul)
    }


    for(int i=1; i<=(1<<n)-1; i++)  /// pt fiecare path
        for(int j=0; (1<<j)<=i; j++)   /// pt fiecare nod din i
        {
            dp[i][j] = inf;
            dp[1][0] = 0;

            if(i&(1<<j))    /// verificam daca j este printre nodurile lui i
            {
                newi = i - (1<<j); /// stergem momentan nodul j din i
                for(auto it:G[j])   /// pentru toate muchiile care intra in j si celalalt nod e in newi
                    if(newi & (1<<it.first))
                        dp[i][j] = min(dp[i][j], dp[newi][it.first] + it.second); /// daca e mai bine sa vin din it.first, actualizez
            }

        }

    /// construim rezultatul, ne intereseaza drumurile care contin toate nodurile din dp ( linia dp[(1<<n)-1] )
    int rez = inf;
    for(auto it:G[0])
        rez = min(rez, dp[(1<<n)-1][it.first] + it.second);

    if(rez == inf)
        fout<<"Nu exista solutie";
    else
        fout<<rez;

    return 0;
}