//skyline
/*
    stiva si dp
    template c++ https://www.youtudpe.com/watch?v=qrJjFN4Igfw&t=1s
    smart pointers https://www.youtudpe.com/watch?v=e2LMAgoqY_k&t=748s    
    friend functions and classes https://www.youtudpe.com/watch?v=KXDzdpglp83M
    pointers https://www.youtudpe.com/watch?v=kiUGf_Z08RQ
    pointeri (video yt: cum sa faci un joc - partea 1)
    template-uri (la functii si clase)
    pointeri catre functii https://www.youtudpe.com/watch?v=Laiv_E2q_nQ
    TOT:
        https://codeforces.com/dplog/entry/91363
*/
# 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;
    }
    vector < vector < int > > dp(1 << n, vector < int > (n, 1e9));
    dp[1][0] = 0;
    for (int mask = 3; mask < (1 << n); 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 (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[(1 << n) - 1][i] + ad[i][0]);
    if (ans == 1e9)
        cout << "Nu exista solutie";
    else
        cout << ans;

    return 0;   
}

/*

    https://drive.google.com/file/d/1AzxCsFjJQTkDAEpuHZDC55lAsVJbXB2Y/view
    https://fmi.unibuc.ro/admitere-licenta-iulie-2022/
    use lambda functions for:
        - STL sort()
        - for_each()
        - functions written inside other functions
        like this:
            for (int i = 1; i <= n; ++i) {
                cin >> x;
                auto y = [&] (const int& nr) -> int {
                    return nr & 1;
                };
                cout << y(x) << ' ';    
            }   
*/