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

class Main {
    static Scanner scanner = new Scanner();
    static int mod = 1000000007;
    static long inf = 0x7ffffffffffffffL;

    public static void main(String[]$) throws Exception {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<List<Grid>> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            edges.add(new ArrayList<>());
            if (i > 0) {
                edges.get(i).add(new Grid(i - 1, 0));
            }
        }
        for (int i = 0; i < m; i++) {
            int l = scanner.nextInt() - 1;
            int r = scanner.nextInt() - 1;
            long c = scanner.nextLong();
            edges.get(l).add(new Grid(r, c));
        }
        long ans = dijkstra(edges, 0)[n - 1];
        System.out.println(ans >= inf ? -1 : ans);
    }

    static long[] dijkstra(List<List<Grid>> edges, int start) {
        long[] cost = new long[edges.size()];
        Arrays.fill(cost, inf);
        cost[start] = 0;

        Queue<Grid> queue = new PriorityQueue<>();
        queue.add(new Grid(start, 0));

        while (!queue.isEmpty()) {
            Grid grid = queue.poll();
            if (cost[grid.to] >= grid.cost) {
                for (Grid g : edges.get(grid.to)) {
                    if (cost[g.to] > cost[grid.to] + g.cost) {
                        cost[g.to] = cost[grid.to] + g.cost;
                        queue.add(new Grid(g.to, cost[g.to]));
                    }
                }
            }
        }
        return cost;
    }

    static class Grid implements Comparable<Grid> {
        int to;
        long cost;

        Grid(int to, long cost) {
            this.to = to;
            this.cost = cost;
        }

        @Override
        public int compareTo(Grid o) {
            return Long.compare(this.cost, o.cost);
        }

        @Override
        public String toString() {
            return String.format("[%s, %s]", to, cost);
        }
    }

    static class System {
        static PrintWriter out = new PrintWriter(java.lang.System.out);

        static {
            Runtime.getRuntime().addShutdownHook(new Thread(System.out::flush));
        }

        static void exit() {
            java.lang.System.exit(0);
        }
    }

    static class Scanner {
        BufferedReader reader = new BufferedReader(new InputStreamReader(java.lang.System.in), 0x10000);
        StringTokenizer tokenizer;

        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }

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

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

        char[][] nextCharArray(int n, int m) {
            char[][] a = new char[n][m];
            for (int i = 0; i < n; i++) {
                a[i] = next().toCharArray();
            }
            return a;
        }
        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        int[] nextIntArray(int n, IntUnaryOperator op) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = op.applyAsInt(nextInt());
            }
            return a;
        }

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

        long[] nextLongArray(int n, LongUnaryOperator op) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = op.applyAsLong(nextLong());
            }
            return a;
        }
    }
}