output_description: 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.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      L_1 R_1 C_1
      :
      L_M R_M C_M
attempt: from heapq import heappush, heappop
  from collections import defaultdict
  
  INF = float("inf")
  
  
  def dijkstra(V, E, s):
      """
      Input:
          V = list(range(N))
          E = defaultdict(dict)
          s (in V) : start vertex
      Output:
          dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
      """
      dist = {v: INF for v in V}
      heap = []
      dist[s] = 0
      rem = len(V)
      heappush(heap, (0, s))
      while heap and rem:
          d, v = heappop(heap)
          # don't need to check when the stored value is greater than provisional distance
          if d > dist[v]:
              continue
          rem -= 1
          for u, c in E[v].items():
              temp = d + c
              if temp < dist[u]:
                  dist[u] = temp
                  heappush(heap, (temp, u))
      return dist
  
  
  N, M = map(int, input().split())
  V = list(range(N))
  E = defaultdict(dict)
  for i in range(N):
      E[i + 1][i] = 0
  for _ in range(M):
      l, r, c = map(int, input().split())
      l, r = l - 1, r - 1
      E[l][r] = min(c, E[l].setdefault(r, INF))
  dist = dijkstra(V, E, 0)
  print(dist[N - 1] if dist[N - 1] != INF else -1)
  
problem_description: Statement
  
  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.
samples: [{"input": "4 3\n    1 3 2\n    2 4 3\n    1 4 6", "output": "5\n    \n\nWe have an edge of length 2 between Vertex 1 and Vertex 2, and an edge of\nlength 3 between Vertex 2 and Vertex 4, so there is a path of length 5 between\nVertex 1 and Vertex 4.\n\n* * *"}, {"input": "4 2\n    1 2 1\n    3 4 2", "output": "-1\n    \n\n* * *"}, {"input": "10 7\n    1 5 18\n    3 4 8\n    1 3 5\n    4 7 10\n    5 9 8\n    6 10 5\n    8 10 3", "output": "28"}]