# include <fstream>
# include <vector>
using namespace std;

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

int main () {

    int n, m;
    cin >> n >> m; 
    vector < vector < int > > to(n), ad(n, vector < int > (n, 1e9)); 
    for (int i = 1; i <= m; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        to[y].push_back(x);
        ad[x][y] = c;
    }
    const int maxx = (1 << n);
    vector < vector < int > > dp(maxx, vector < int > (n, 1e9));
    dp[1][0] = 0;
    for (int mask = 3; mask < maxx; mask += 2) // iau toate traseele posibile cu ultimul bit setat 
        for (int curr_node = 1; curr_node < n; ++curr_node) // iau toate nodurile
            if (mask & (1 << curr_node))
                for (const auto& neighbour: to[curr_node])
                    dp[mask][curr_node] = min(dp[mask][curr_node], dp[mask ^ (1 << curr_node)][neighbour] + ad[neighbour][curr_node]);
    int ans(1e9);
    for (int i = 1; i < n; ++i)
        ans = min(ans, dp[maxx - 1][i] + ad[i][0]);
    if (ans == 1e9)
        cout << "Nu exista solutie";
    else
        cout << ans;

    return 0;   
}