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.*;

public class Main {
    static int N;
    static int M;
    static long[] d;
    static List<List<Edge>> edges;
    public static void main(String[] args) {
        N = sc.nextInt();
        M = sc.nextInt();
        d = new long[N];
        edges = new ArrayList<List<Edge>>(N);
        for (int i = 0; i < N; i++) {
            edges.add(new ArrayList<Edge>());
            if (i > 0) {
                edges.get(i).add(new Edge(i - 1, 0));
            }
        }
        for (int i = 0; i < M; i++) {
            int l = sc.nextInt() - 1;
            int r = sc.nextInt() - 1;
            long c = sc.nextLong();
            edges.get(l).add(new Edge(r, c));
        }
        for (int i = 0; i < N; i++) d[i] = Long.MAX_VALUE;
        //Dijkstra 
        PriorityQueue<Vertex> pq = new PriorityQueue<Vertex>();
        pq.add(new Vertex(0,0));
        boolean[] finalized = new boolean[N];
        while (pq.size() > 0) {
            Vertex v = pq.poll();
            if(finalized[v.id]) continue;
            finalized[v.id] = true;
            d[v.id] = Math.min(d[v.id],v.distance);
            for (Edge edge : edges.get(v.id)) {
                long newCost = d[v.id] + edge.cost;
                if (finalized[edge.dest]) continue;
                pq.add(new Vertex(edge.dest, newCost));
            }
        }
        long answer;
        if (d[N-1] == Long.MAX_VALUE) {
            answer = -1;
        } else {
            answer = d[N-1];
        }
        // writer.println(Arrays.toString(d));
        writer.println(answer);
        writer.flush();
    }

    public static class Edge {
        public int dest;
        public long cost;
        public Edge(int d, long c) {
            this.dest = d;
            this.cost = c;
        }
    }

    public static class Vertex implements Comparable<Vertex> {
        public int id;
        public long distance;

        public Vertex(int id, long distance) {
            this.id = id;
            this.distance = distance;
        }

        public int compareTo(Vertex v) {
            if (this.distance < v.distance) return -1;
            if (this.distance > v.distance) return 1;
            return 0;
        }

    }

    static final FastScanner sc = new FastScanner(System.in);
    static PrintWriter writer = new PrintWriter(System.out);

    static class FastScanner {
        Reader input;
 
        FastScanner() {
            this(System.in);
        }
 
        FastScanner(InputStream stream) {
            this.input = new BufferedReader(new InputStreamReader(stream));
        }
 
        int nextInt() {
            return (int) nextLong();
        }
 
        long nextLong() {
            try {
                int sign = 1;
                int b = input.read();
                while ((b < '0' || '9' < b) && b != '-' && b != '+') {
                    b = input.read();
                }
                if (b == '-') {
                    sign = -1;
                    b = input.read();
                } else if (b == '+') {
                    b = input.read();
                }
                long ret = b - '0';
                while (true) {
                    b = input.read();
                    if (b < '0' || '9' < b) return ret * sign;
                    ret *= 10;
                    ret += b - '0';
                }
            } catch (IOException e) {
                e.printStackTrace();
                return -1;
            }
        }
 
        double nextDouble() {
            try {
                double sign = 1;
                int b = input.read();
                while ((b < '0' || '9' < b) && b != '-' && b != '+') {
                    b = input.read();
                }
                if (b == '-') {
                    sign = -1;
                    b = input.read();
                } else if (b == '+') {
                    b = input.read();
                }
                double ret = b - '0';
                while (true) {
                    b = input.read();
                    if (b < '0' || '9' < b) break;
                    ret *= 10;
                    ret += b - '0';
                }
                if (b != '.') return sign * ret;
                double div = 1;
                b = input.read();
                while ('0' <= b && b <= '9') {
                    ret *= 10;
                    ret += b - '0';
                    div *= 10;
                    b = input.read();
                }
                return sign * ret / div;
            } catch (IOException e) {
                e.printStackTrace();
                return Double.NaN;
            }
        }
 
        char nextChar() {
            try {
                int b = input.read();
                while (Character.isWhitespace(b)) {
                    b = input.read();
                }
                return (char) b;
            } catch (IOException e) {
                e.printStackTrace();
                return 0;
            }
        }
 
        String nextStr() {
            try {
                StringBuilder sb = new StringBuilder();
                int b = input.read();
                while (Character.isWhitespace(b)) {
                    b = input.read();
                }
                while (b != -1 && !Character.isWhitespace(b)) {
                    sb.append((char) b);
                    b = input.read();
                }
                return sb.toString();
            } catch (IOException e) {
                e.printStackTrace();
                return "";
            }
        }
    }
    //FAST SCANNER END HERE
}