Problem: Problem

There are N islands and M bridges. Numbers from 1 to N are assigned to each of the N islands. Numbers from 1 to M are also assigned to each of the M bridges.

Gaccho is currently on the first island (at time 0). Gaccho can move from the ai-th island to the bi-th island in one direction by using the i-th bridge.

However, at time 0, all the bridges were full of tide and sank into the sea. The i-th bridge will be able to cross the tide at time ci. And soon after the time ci, the tide rises again and the i-th bridge sinks again. When it sinks again, I don't know when the tide will pull and cross. So, Gaccho decided to think that such a bridge would never be crossed.

Gaccho wants to see the scenery of the 1st to N-1st islands for as long as possible, but since he is staying at the Nth island, he finally arrives at the Nth island. There must be. Also, because he keeps his parents waiting on the boat, Gacho must leave by boat and go home as soon as he arrives at the Nth island.

The time it takes for Gaccho to cross the bridge and travel around the island is very short, so you can assume it is 0. Find the maximum amount of time Gaccho can be on any of the 1st to N-1 islands. However, if you can't move to the Nth island no matter how you move, output -1 instead.

Constraints

* 2 ≤ N ≤ 105
* 1 ≤ M ≤ 2 × 105
* 1 ≤ ai <N
* 1 ≤ bi ≤ N
* 1 ≤ ci ≤ 109
* ai ≠ bi

Input

The input is given in the following format.


N M
a1 b1 c1
a2 b2 c2
...
aM bM cM


On the first line, two integers N and M are given, separated by blanks.
Three integers ai, bi, ci are given in each line i from the second line to the M + 1 line, separated by blanks.

Output

If Gaccho can move to the Nth island, it will output the maximum amount of time that Gaccho can be on any of the 1st to N-1th islands. If it cannot move to the Nth island, it prints -1 instead.

Examples

Input

3 2
1 2 10
2 3 20


Output

20


Input

4 4
1 2 27
1 3 37
2 3 47
3 1 57


Output

-1


Input

3 3
1 2 13
2 3 17
2 3 15


Output

17


Input

3 2
1 2 20
2 3 10


Output

-1


Input

3 2
1 2 10
2 3 10


Output

10

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

#define int long long

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)
#define rep1(i,x) for(int i=1;i<=(int)(x);++i)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T>T& max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T& min(T&a,T&b){if(a<b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T get(){T a;cin>>a;return a;}
template<typename T>T rev(T a){reverse(all(a));return a;}
template<typename T>vector<T>&sort(vector<T>&a){sort(all(a));return a;}

const int inf = 3e18;
const double eps = 1e-9;

struct edge { int to, cost; edge(int to, int cost) : to(to), cost(cost) {} };
typedef vector<edge> edges;

edges G[100010];

int d[100010];
int to_max[100010];

signed main()
{ // #define int long long ?????????????????§scanf???????????¨???????????????????????\?????????????????????
    int N, M; cin >> N >> M;

    fill_n(to_max, 100010, -1);
    fill_n(d, 100010, inf);

    rep(i, M) {
        int a, b, c; cin >> a >> b >> c;
        G[a].PB(edge(b, c));

        if (b == N) {
            chmax(to_max[a], c);
        }
    }

    priority_queue<pii, vpii, greater<pii> > pq;

    pq.push(pii(0, 1));
    d[1] = 0;

    while (pq.size()) {
        pii p = pq.top(); pq.pop();

        int v = p.scd;

        if (d[v] < p.fst) continue;

        for (int i = 0; i < G[v].size(); ++i) {
            edge e = G[v][i];

            if (d[e.to] > e.cost && d[v] <= e.cost) {
                d[e.to] = e.cost;
                pq.push(pii(d[e.to], e.to));
            }
        }
    }

    int ans = -1;

    if (d[N] != inf) {
        for (int i = 1; i <= N; ++i) {
            if (d[i] != inf && d[i] <= to_max[i]) {
                chmax(ans, to_max[i]);
            }
        }
    }

    cout << ans << endl;
}