#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(false);cout.precision(30);cout.tie(0);cin.tie(0);
#define ll long long
#define ld long double
#define rep(i, a, b) for(__typeof(b)i=(a)-((a)>(b));i!=(b)-((a)>(b));i+=1-2*((a)>(b)))
#define whilet() ll t;cin>>t;while(t--)
#define all(c) (c).begin(), (c).end()
 
ifstream fi("hamilton.in");
ofstream fo("hamilton.out");
 
template <class TCost>
class Graph {
public:
    struct Edge {
        long from, to;
        TCost cost;
        Edge(long _from, long _to, TCost _cost): from(_from), to(_to), cost(_cost) {};
    };
    long size;
    bool zeroIndexed;
    vector<Edge> edges;
    vector<vector<pair<long, TCost>>> adjacencyList;
    Graph() {};
    Graph(long _size, bool _zeroIndexed = true) {
        zeroIndexed = _zeroIndexed;
        if (!zeroIndexed) _size++;
        size = _size;
        adjacencyList.resize(_size);
    };
    ~Graph() = default;
};
template <class TCost>
class DirectedGraph : public Graph<TCost> {
public:
    using typename Graph<TCost>::Edge;
    vector<vector<Edge>> inEdges;
    DirectedGraph() {};
    DirectedGraph(long _size, bool _zeroIndexed): Graph<TCost>(_size, _zeroIndexed) {};
    DirectedGraph(long _size): Graph<TCost>(_size) {};
    void addEdge(long from, long to, TCost cost = 0) {
        this->edges.push_back({from, to, cost});
        this->adjacencyList[from].push_back({to, cost});
    }
    void printEdges() {
        for (auto edge: this->edges) {
            cout << edge.from << ' ' << edge.to << endl;
        }
    }
    void buildInEdges() {
        inEdges.resize(this->size);
        for (Edge u: this->edges) {
            inEdges[u.to].push_back(u);
        }
    }
};
class Hamilton {
public:
    static vector<long> defaultPath;
    template <class TCost>
    static TCost cost(DirectedGraph<TCost> graph) {
        vector<vector<long long>> dp(1<<graph.size, vector<long long>(graph.size));
        graph.buildInEdges();
        for (int i=1; i<(1<<graph.size); i++) {
            for (int v=(graph.zeroIndexed?0:1); v<graph.size; v++) {
                dp[i][v] = INT32_MAX;
            }
        }
        dp[1][0] = 0;
        for (int i=1; i<(1<<graph.size); i++) {
            for (int v=(graph.zeroIndexed?0:1); v<graph.size; v++) {
                if (!(i&(1<<v))) continue;
                for (auto u: graph.inEdges[v]) {
                    if (!(i&(1<<u.from))) continue;
                    dp[i][v] = min(dp[i][v], dp[(i^(1<<v))][u.from]+(int)u.cost);
                }
            }
        }

        TCost rs = INT32_MAX;
        for (auto u:graph.inEdges[0]) {
            rs = min(rs, dp[(1<<graph.size)-1][u.from]+u.cost);
        }

        return rs;
    }
    template <class TCost>
    static TCost costWithPath(DirectedGraph<TCost> graph, bool minPath = true, vector<long> &path = defaultPath) {
        vector<vector<long long>> dp(1<<graph.size, vector<long long>(graph.size));
        vector<vector<long>> pathParent(1<<graph.size, vector<long>(graph.size));
        graph.buildInEdges();
        for (int i=1; i<(1<<graph.size); i++) {
            for (int v=(graph.zeroIndexed?0:1); v<graph.size; v++) {
                dp[i][v] = minPath?INT32_MAX:INT32_MIN;
            }
        }
        dp[1][0] = 0;
        for (int i=1; i<(1<<graph.size); i++) {
            for (int v=(graph.zeroIndexed?0:1); v<graph.size; v++) {
                if (!(i&(1<<v))) continue;
                for (auto u: graph.inEdges[v]) {
                    if (!(i&(1<<u.from))) continue;
                    if (dp[(i ^ (1 << v))][u.from] == INT32_MIN) continue;
                    if (dp[(i ^ (1 << v))][u.from] == INT32_MAX) continue;
                    long long newCost = dp[(i ^ (1 << v))][u.from] + (int) u.cost;
                    if (minPath) {
                        if (dp[i][v] > newCost) {
                            dp[i][v] = newCost;
                            pathParent[(i ^ (1 << v))][v] = u.from;
                        }
                    } else {
                        if (dp[i][v] < newCost) {
                            dp[i][v] = newCost;
                            pathParent[(i ^ (1 << v))][v] = u.from;
                        }
                    }
                }
            }
        }
 
 
        TCost rs = minPath?INT32_MAX:INT32_MIN;
        for (auto u:graph.inEdges[0]) {
            if (dp[(1<<graph.size)-1][u.from] == INT32_MIN) continue;
            if (dp[(1<<graph.size)-1][u.from] == INT32_MAX) continue;
            long long newCost = dp[(1<<graph.size)-1][u.from]+u.cost;
            if (minPath) {
                if (newCost < rs) {
                    rs = newCost;
                    pathParent[(1<<graph.size)-1][0] = u.from;
                }
            } else {
                if (newCost > rs) {
                    rs = newCost;
                    pathParent[(1<<graph.size)-1][0] = u.from;
                }
            }
        }
 
        // make path
        long start = 0;
        long long i = (1<<graph.size)-1;
        path.push_back(0);
        do {
            path.push_back(pathParent[i][start]);
            start = pathParent[i][start];
            i = i^(1<<start);
        } while (start != 0);
 
        reverse(path.begin(),path.end());
 
        return rs;
    }
};
 
int main() {_
    ll n,m;
    fi >> n >> m;
    DirectedGraph<ll> graph = DirectedGraph<ll>(n);
    for (int i=0; i<m; i++) {
        ll x,y,v;
        fi >> x >> y >> v;
        graph.addEdge(x,y,v);
    }
 

    vector<long> path;
    ll rs = Hamilton::costWithPath(graph, true, path);
    if (rs == 100000000) fo << "Nu exista solutie"; else fo << rs;
 
    return 0;
}