#include<cstdio>
    #include<vector>
    using namespace std;
    #define MAX 300000
    #define pb push_back
    #define INF 325000000
    int N , M  , cost[20][20] , c[MAX][20] , minn;
    vector<int> G[20];

    void citire();
    void solve();
    void tipar();

    int main()
    {
        citire();
        solve();
        tipar();
        return 0;
    }

    void citire()
    {
        int x , y , z;
        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 , &z);
            G[y].pb(x);
            cost[x][y] = z;
        }
    }

    void solve()
    {
        for(int i = 1 ; i < (1<<N) ; ++i )
            for(int j = 0 ; j < N ; ++j )
                c[i][j] = INF;
        c[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(c[i][j] > c[i^(1<<j)][G[j][k]] + cost[G[j][k]][j])
                            c[i][j] = c[i^(1<<j)][G[j][k]] + cost[G[j][k]][j];
        minn = INF;
        for(int i = 0 ; i < (int)G[0].size() ; ++i )
            if(minn > c[(1<<N)-1][G[0][i]] + cost[G[0][i]][0])
                minn = c[(1<<N)-1][G[0][i]] + cost[G[0][i]][0];
    }

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