#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

ifstream cin ("hamilton.in");
ofstream cout ("hamilton.out");

const int MAX = (1 << 18);
int gr[20][20];
vector <int> mask [20];
int dp [MAX + 5][20];

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int nodes , edges;
    cin>>nodes>>edges;

    for (int i=1; i<=edges; i++){
        int a , b , val;
        cin>>a>>b>>val;
        gr[a][b] = val;
    }

    for (int masc=0; masc<(1 << nodes); masc++){
        int cont = 0;
        for (int bit = 0; bit < nodes; bit++){
            if (masc & (1 << bit)){
                cont ++;
            }
        }
        mask[cont].push_back(masc);
    }

    for (int i=0; i<=nodes; i++){
        for (int j=0; j<nodes; j++){
            dp[(1 << i)][j] = INT_MAX;
        }
    }
    dp[1][0] = 0;

    for (int i=1; i<=nodes; i++){
        for (auto &x : mask[i]){
            for (int l=0; l<nodes; l++){
                if (dp[x][l] != INT_MAX){
                    for (int bit = 0; bit<nodes; bit++){
                        if ((!(x & (1 << bit))) && gr[l][bit] != 0){
                            if (dp[x + (1 << bit)][bit] > dp[x][l] + gr[l][bit]){
                                dp[x + (1 << bit)][bit] = dp[x][l] + gr[l][bit];
                            }
                        }
                    }
                }
            }
        }
    }

    int MIN = INT_MAX;
    for (int l=0; l<nodes; l++){
        if (dp[(1 << nodes) - 1][l] != INT_MAX && gr[l][0] != 0){
            MIN = min(MIN , dp[(1 << nodes) - 1][l] + gr[l][0]);
        }
    }

    if (MIN == INT_MAX){
        cout<<"Nu exista solutie";
        return 0;
    }
    cout<<MIN;

    return 0;
}