Problem: The pandemic is upon us, and the world is in shortage of the most important resource: toilet paper. As one of the best prepared nations for this crisis, BubbleLand promised to help all other world nations with this valuable resource. To do that, the country will send airplanes to other countries carrying toilet paper.

In BubbleLand, there are N toilet paper factories, and N airports. Because of how much it takes to build a road, and of course legal issues, every factory must send paper to only one airport, and every airport can only take toilet paper from one factory.

Also, a road can't be built between all airport-factory pairs, again because of legal issues. Every possible road has number d given, number of days it takes to build that road.

Your job is to choose N factory-airport pairs, such that if the country starts building all roads at the same time, it takes the least amount of days to complete them.

Input

The first line contains two integers N (1 ≤ N ≤ 10^4) - number of airports/factories, and M (1 ≤ M ≤ 10^5) - number of available pairs to build a road between.

On next M lines, there are three integers u, v (1 ≤ u,v ≤ N), d (1 ≤ d ≤ 10^9) - meaning that you can build a road between airport u and factory v for d days.

Output

If there are no solutions, output -1. If there exists a solution, output the minimal number of days to complete all roads, equal to maximal d among all chosen roads.

Example

Input


3 5
1 2 1
2 3 2
3 3 3
2 1 4
2 2 5


Output


4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <class T>
bool ckmin(T& a, const T& b) {
  return a > b ? a = b, true : false;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, true : false;
}
template <typename T>
struct IsC {
  template <typename C>
  static char test(typename C::const_iterator*);
  template <typename C>
  static int test(...);
  static const bool value = sizeof(test<T>(0)) == sizeof(char);
};
template <>
struct IsC<string> {
  static const bool value = false;
};
template <typename C>
typename enable_if<IsC<C>::value, ostream&>::type operator<<(ostream&,
                                                             const C&);
template <typename T1, typename T2>
ostream& operator<<(ostream&, const pair<T1, T2>&);
template <typename... T>
using TS = tuple_size<tuple<T...>>;
template <size_t idx, typename... T>
typename enable_if<TS<T...>::value == idx + 1, ostream&>::type operator<<(
    ostream& o, const tuple<T...>& t) {
  return o << ", " << get<idx>(t) << ')';
}
template <size_t idx, typename... T>
typename enable_if<0 < idx && idx + 1 < TS<T...>::value, ostream&>::type
operator<<(ostream& o, const tuple<T...>& t) {
  return operator<<<idx + 1>(o << ", " << get<idx>(t), t);
}
template <size_t idx = 0, typename... T>
typename enable_if<1 < TS<T...>::value && !idx, ostream&>::type operator<<(
    ostream& o, const tuple<T...>& t) {
  return operator<<<idx + 1>(o << '(' << get<idx>(t), t);
}
template <typename T>
ostream& operator<<(ostream& o, const tuple<T>& t) {
  return o << get<0>(t);
}
template <typename T1, typename T2>
ostream& operator<<(ostream& o, const pair<T1, T2>& p) {
  return o << make_tuple(p.first, p.second);
}
template <typename C>
typename enable_if<IsC<C>::value, ostream&>::type operator<<(ostream& o,
                                                             const C& c) {
  o << '[';
  for (auto it = c.cbegin(); it != c.cend(); ++it)
    o << *it << (next(it) != c.cend() ? ", " : "");
  return o << ']';
}
template <typename T>
void tprint(vector<vector<T>>& v, size_t width = 0, ostream& o = cerr) {
  if (!0) return;
  for (const auto& vv : v) {
    for (const auto& i : vv) o << setw(width) << i;
    o << '\n';
  }
}
struct edge {
  edge(int from, int to, long long capacity, long long flow = 0)
      : mfrom(from), mto(to), mcapacity(capacity), mflow(flow) {}
  int mfrom, mto;
  long long mcapacity, mflow;
  int other(int v) { return v == mfrom ? mto : mfrom; }
  long long capacity(int v) { return v == mfrom ? mcapacity : 0; }
  long long flow(int v) { return v == mfrom ? mflow : -mflow; }
  void adjust(int v, long long amount) {
    mflow += v == mfrom ? amount : -amount;
  }
};
vector<edge> edges;
vector<long long> edgeWgt;
vector<vector<int>> adj;
void addEdge(int from, int to, long long c, long long f = 0) {
  edges.emplace_back(from, to, 1, f);
  adj[from].push_back((int)(edges).size() - 1);
  adj[to].push_back((int)(edges).size() - 1);
  edgeWgt.push_back(c);
}
ostream& operator<<(ostream& o, const edge& e) {
  return o << e.mfrom << "-- " << e.mflow << '/' << e.mcapacity << " -->"
           << e.mto;
}
const int INTINF = 1e9 + 10;
const long long INF = 1e18;
long long cantUse = 1e9 + 10;
vector<int> dist, ptr;
const long long inf = 1e16;
bool dinic_bfs(int s, int t) {
  dist.assign((int)(adj).size(), (int)(adj).size());
  queue<int> q;
  q.push(s);
  dist[s] = 0;
  while ((int)(q).size()) {
    int v = q.front();
    q.pop();
    for (int i : adj[v]) {
      edge& e = edges[i];
      if (edgeWgt[i] > cantUse) continue;
      if (dist[e.other(v)] == (int)(adj).size() && e.flow(v) < e.capacity(v)) {
        dist[e.other(v)] = dist[v] + 1;
        q.push(e.other(v));
      }
    }
  }
  return dist[t] < (int)(adj).size();
}
long long dinic_dfs(int v, int t, long long available) {
  if (v == t || !available) return available;
  long long pushed = 0;
  for (; ptr[v] < (int)(adj[v]).size(); ++ptr[v]) {
    if (edgeWgt[adj[v][ptr[v]]] > cantUse) continue;
    edge& e = edges[adj[v][ptr[v]]];
    if (dist[v] + 1 != dist[e.other(v)]) continue;
    long long wasPushed = dinic_dfs(
        e.other(v), t, min(available - pushed, e.capacity(v) - e.flow(v)));
    pushed += wasPushed;
    e.adjust(v, wasPushed);
    if (pushed == available) return pushed;
  }
  return pushed;
}
long long maxflow(int s, int t) {
  long long f = 0;
  while (1) {
    if (!dinic_bfs(s, t)) return f;
    ptr.assign((int)(adj).size(), 0);
    f += dinic_dfs(s, t, inf);
  }
}
void solve() {
  int n, m;
  cin >> n >> m;
  adj = vector<vector<int>>(2 * n + 2);
  int source = 2 * n + 1;
  int target = 2 * n;
  for (auto i = (0); (i) < ((m)); ++(i)) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    addEdge(a, n + b, c);
  }
  for (auto i = (0); (i) < ((n)); ++(i)) {
    addEdge(source, i, 0);
    addEdge(n + i, target, 0);
  }
  long long l = 0, r = INTINF;
  while (l < r) {
    for (edge& e : edges) e.mflow = 0;
    cantUse = (l + r) / 2;
    if (maxflow(source, target) == n)
      r = cantUse;
    else
      l = cantUse + 1;
  }
  cout << (l == INTINF ? -1 : l) << '\n';
}
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  if (0) cerr << boolalpha;
  int tc = 1;
  for (auto i = (1); (i) < (tc + 1); ++(i)) {
    solve();
  }
}