#include <fstream>
#include <vector>
#define INF (1 << 30) - 1
std::ifstream fin("hamilton.in");
std::ofstream fout("hamilton.out");
int n, m, dp[(1 << 19)][19];
std::vector<std::vector<std::pair<int, int>>> back;
void minRoad(){

    for(int i = 0; i < (1 << n); i++){
        for(int j = 0; j <= 18; j++){
            dp[i][j] = INF;
        }
    }
    dp[1][0] = 0;
    for(int i = 1; i < (1 << n); i++){
        for(int j = 0; j < n; j++){
            if(i & (1 << j)){
                for(std::pair<int, int> it : back[j])
                    if(i & (1 << it.first)){
                        dp[i][j] = std::min(dp[i ^ (1 << j)][it.first] + it.second, dp[i][j]);
                        //fout << dp[i][j] << " " << dp[i ^ (1 << j)][it.first] << " " << " " << i << " " << j << " " << (i ^ (1 << j)) << "\n";
                    }
            }
        }
    }
    int res = INF;
    for(std::pair<int, int> it : back[0]){
        res = std::min(res, dp[(1 << n) - 1][it.first] + it.second);
    } 
    
    if(res == INF) fout << "Nu exista solutie";
    else fout << res;
}
int main(){
    fin >> n >> m;
    back = std::vector<std::vector<std::pair<int, int>>> (n + 1);
    for(int i = 1; i <= m; i++){
        int x, y, c;
        fin >> x >> y >> c;
        back[y].push_back({x, c});
    }
    minRoad();
}