#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

const int INF = 1e8;

int n,m,x,y,c;
vector<vector<pair<int,int>>> adj;

typedef tuple<int,int,int> State;

int main(){
    f >> n >> m;

    adj.resize(n);
    vector<vector<int>> dist(1 << n, vector<int>(n+1,INF));
    priority_queue<State, vector<State>, greater<State>> pq;

    for(int i=1; i<=m; i++){
        f >> x >> y >> c;
        adj[x].push_back(make_pair(y,c));
    }

    // {costMinimPanaLaNodCurent, mascaCurenta, nodCurent}
    pq.push({0,1 << 0,0});
    dist[1 << 0][0] = 0;

    while(!pq.empty()){
        auto [wt, mask, nod] = pq.top();
        pq.pop();

        if(wt > dist[mask][nod])
            continue;

        if(mask == ((1 << n)-1)){
            for(auto& [neigh,cost]: adj[nod]){
                if(neigh == 0){
                    g << wt + cost;
                    return 0;
                    // dist[mask][neigh] = wt + cost;
                    // break;
                }
            }
        }

        for(auto& [neigh, costCrt]: adj[nod]){

            if((mask >> neigh) & 1){
                continue;
            }

            int newMask = mask | (1 << neigh);

            if(dist[newMask][neigh] > costCrt + wt){
                dist[newMask][neigh] = costCrt + wt;
                pq.push({dist[newMask][neigh], newMask, neigh});
            }
        }
    }
    g << -1;

    return 0;
}