#include<cstdio>
    #include<vector>
    #include<iostream>
    using namespace std;
    #define MAX 19
    #define INF 310000000
    #define pb push_back
    int N , M , d[1<<MAX][MAX] , cost[MAX][MAX] , minn ;
    vector<int> G[MAX];

    void read();
    void solve();
    void write();

    int main()
    {
        read();
        solve();
        write();
        return 0;
    }

    void read()
    {
        int x , y , w;
        freopen("hamilton.in" , "r" , stdin );
        scanf("%d%d" , &N , &M );
        for(int i = 0 ; i < N ; ++i )
            for(int j = 0 ; j < N ; ++j )
                cost[i][j] = INF;
        for(int i = 1 ; i<= M ; ++i )
        {
            scanf("%d%d%d" , &x , &y , &w );
            cost[x][y] = w;
            G[y].pb(x);
        }
    }

    void solve()
    {
        for(int i  = 1 ; i < (1<<N) ; ++i )
            for(int j = 0 ; j < N ; ++j )
                d[i][j] =INF;
        d[1][0] = 0;
        for(int i = 1 ; i< (1<<N) ; ++i )
        {
            for(int j = 0 ; j < N ; ++j )
                if(i&(1<<j))
                for(int k = 0 ; k <(int)G[j].size() ; ++k )
                    if(i&(1<<G[j][k]))
                    d[i][j] = min (d[i][j] , d[i^(1<<j)][G[j][k]] + cost[G[j][k]][j]);
        }
        minn = INF;
        for(int k = 0 ; k < (int)G[0].size() ; ++k )
            minn = min(minn , d[(1<<N)-1][G[0][k]] + cost[G[0][k]][0]);
    }

    void write()
    {
        freopen("hamilton.out" , "w" , stdout );
        if(minn != INF)
            printf("%d" , minn );
        else
            printf("Nu exista solutie");
    }