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.OutputStream;
import java.io.PrintWriter;
import java.util.*;

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
            pass System Test!
*/
@SuppressWarnings("unchecked")
public class Main {
  private static class Task {
    class Edge implements Comparable<Edge> {
      int to, time;
      Edge(int to, int time) {
        this.time = time;
        this.to = to;
      }
      @Override
      public int compareTo(Edge o) {
        return this.time - o.time;
      }
    }

    void solve(FastScanner in, PrintWriter out) {
      int N = in.nextInt();
      int M = in.nextInt();
      ArrayList<Edge>[] graph = new ArrayList[N];
      for (int i = 0; i < N; i++) graph[i] = new ArrayList<>();
      for (int i = 0; i < M; i++) {
        int a = in.nextInt() - 1;
        int b = in.nextInt() - 1;
        int c = in.nextInt();
        graph[a].add(new Edge(b, c));
      }

      int max = -1;
      boolean[] vis = new boolean[N];

      PriorityQueue<Edge> queue = new PriorityQueue<>();
      queue.add(new Edge(0, 0));
      while (!queue.isEmpty()) {
        Edge state = queue.poll();
        if (vis[state.to]) continue;
        vis[state.to] = true;
        for (Edge edge : graph[state.to]) {
          if (edge.time < state.time) continue;
          if (edge.to == N - 1) {
            max = Math.max(max, edge.time);
            continue;
          }
          queue.add(edge);
        }
      }
      out.println(max);
    }
  }

  /**
   * ?????????????????????????????¬????????§??????
   */
  public static void main(String[] args) {
    OutputStream outputStream = System.out;
    FastScanner in = new FastScanner();
    PrintWriter out = new PrintWriter(outputStream);
    Task solver = new Task();
    solver.solve(in, out);
    out.close();
  }
  private static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

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

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

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

    long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

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

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; i++) array[i] = nextInt();
      return array;
    }

    public long[] nextLongArray(int n) {
      long[] array = new long[n];
      for (int i = 0; i < n; i++) array[i] = nextLong();
      return array;
    }

    public String[] nextStringArray(int n) {
      String[] array = new String[n];
      for (int i = 0; i < n; i++) array[i] = next();
      return array;
    }

    public char[][] nextCharMap(int n) {
      char[][] array = new char[n][];
      for (int i = 0; i < n; i++) array[i] = next().toCharArray();
      return array;
    }

    public int[][] nextIntMap(int n, int m) {
      int[][] map = new int[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextIntArray(m);
      }
      return map;
    }
  }
}