Problem: We have N points numbered 1 to N arranged in a line in this order.

Takahashi decides to make an undirected graph, using these points as the vertices. In the beginning, the graph has no edge. Takahashi will do M operations to add edges in this graph. The i-th operation is as follows:

* The operation uses integers L_i and R_i between 1 and N (inclusive), and a positive integer C_i. For every pair of integers (s, t) such that L_i \leq s < t \leq R_i, add an edge of length C_i between Vertex s and Vertex t.



The integers L_1, ..., L_M, R_1, ..., R_M, C_1, ..., C_M are all given as input.

Takahashi wants to solve the shortest path problem in the final graph obtained. Find the length of the shortest path from Vertex 1 to Vertex N in the final graph.

Constraints

* 2 \leq N \leq 10^5
* 1 \leq M \leq 10^5
* 1 \leq L_i < R_i \leq N
* 1 \leq C_i \leq 10^9

Input

Input is given from Standard Input in the following format:


N M
L_1 R_1 C_1
:
L_M R_M C_M


Output

Print the length of the shortest path from Vertex 1 to Vertex N in the final graph. If there is no shortest path, print `-1` instead.

Examples

Input

4 3
1 3 2
2 4 3
1 4 6


Output

5


Input

4 2
1 2 1
3 4 2


Output

-1


Input

10 7
1 5 18
3 4 8
1 3 5
4 7 10
5 9 8
6 10 5
8 10 3


Output

28

Solution (in JAVA):

Solution:
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static Scanner sc = new Scanner(System.in);
    static final long INF = Long.MAX_VALUE / 4;

    public static void main(String[] args) {
        int N = sc.nextInt();
        int M = sc.nextInt();
        SegTree st = new SegTree(N);
        Edge[] edges = new Edge[M];
        for (int i = 0; i < M; i++) {
            int L = sc.nextInt() - 1;
            int R = sc.nextInt() - 1;
            int C = sc.nextInt();
            edges[i] = new Edge(L, R, C);
        }
        Arrays.sort(edges);
        for (int i = 0; i < M; i++) {
            Edge e = edges[i];
            long s = st.get(e.l);
            if (s == INF) {
                System.out.println(-1);
                return;
            }
            st.add(e.l + 1, e.r + 1, s + e.c);
        }
        long ans = st.get(N - 1);
        System.out.println(ans == INF ? -1 : ans);
    }

    static class Edge implements Comparable<Edge> {
        int l, r, c;

        public Edge(int l, int r, int c) {
            this.l = l;
            this.r = r;
            this.c = c;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.l, o.l);
        }
    }

    static class SegTree {

        int size;
        long[] tree;

        SegTree(int size) {
            this.size = size;
            int l = 1;
            while (l < size * 2) {
                l *= 2;
            }
            tree = new long[l];
            Arrays.fill(tree, INF);
            add(0, 1, 0);
        }

        void add(int lo, int hi, long v) {
//            System.err.println("add:" + lo + " " + hi + " " + v);
            add(0, 0, size, lo, hi, v);
        }

        private void add(int idx, int left, int right, int lo, int hi, long v) {
            if (lo <= left && right <= hi) {
                tree[idx] = Math.min(tree[idx], v);
                return;
            }
            int mid = (left + right) / 2;
            if (lo < mid) add(idx * 2 + 1, left, mid, lo, hi, v);
            if (mid < hi) add(idx * 2 + 2, mid, right, lo, hi, v);
        }

        long get(int pos) {
            return get(0, 0, size, pos);
        }

        private long get(int idx, int left, int right, int pos) {
//            System.err.println("get:" + idx + " " + left + " " + right + " " + pos);
            if (pos < left || right <= pos) return Long.MAX_VALUE;
            long ret = tree[idx];
            if (right - left == 1) return ret;
            int mid = (left + right) / 2;
            if (pos < mid) ret = Math.min(ret, get(idx * 2 + 1, left, mid, pos));
            if (mid <= pos) ret = Math.min(ret, get(idx * 2 + 2, mid, right, pos));
            return ret;
        }
    }
}