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 JAVA):

Solution:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;

public class Main {
	int N, M;
	ArrayList<ArrayList<E>> graph;

	private class E implements Comparable<E>{
		int v, c;
		public E(int v, int c) {
			this.v = v;
			this.c = c;
		}

		public int compareTo(E e){
			return this.c - e.c;
		}
	}
	public void solve() {
		N = nextInt();
		M = nextInt();
		graph = new ArrayList<ArrayList<E>>();
		for (int i = 0; i < N; i++) {
			graph.add(new ArrayList<E>());
		}
		for (int i = 0; i < M; i++) {
			int a = nextInt() - 1;
			int b = nextInt() - 1;
			int c = nextInt();
			graph.get(a).add(new E(b, c));
		}

		PriorityQueue<E> pq = new PriorityQueue<E>();
		boolean[] used = new boolean[N];
		int ans = -1;
		pq.add(new E(0,0));
		while(pq.size() > 0){
			E  e = pq.poll();

			if(e.v == N - 1){
				ans = Math.max(ans, e.c);
			}

			if(used[e.v])continue;
			used[e.v] = true;

			for(E ee : graph.get(e.v)){
				if(e.c <= ee.c){
					pq.add(new E(ee.v,ee.c));
				}
			}
		}
		out.println(ans);
	}

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}