#=== Template_Base =========================== {{{

import strutils, sequtils, math, algorithm, macros
when (not (NimMajor <= 0)) or NimMinor >= 19:
  import sugar
else:
  import future

# type
#   si = seq[int]
#   ssi = seq[seq[int]]
#   sf = seq[float]
#   ssf = seq[seq[float]]

# proc r(): string = stdin.readLine
# proc ri(): int = r().parseInt
# proc rsi(): seq[int] = r().split.map(parseInt)
# proc rf(): float = r().parseFloat
# proc rsf(): seq[float] = r().split.map(parseFloat)
# proc rn(n: int): seq[string] =
#   result = @[]
#   for i in 1..n:
#     result.add(r())
# proc rin(n: int): seq[int] =
#   result = @[]
#   for i in 1..n:
#     result.add(ri())
# proc rsin(n: int): seq[seq[int]] =
#   result = @[]
#   for i in 1..n:
#     result.add(rsi())
iterator range(x, y: int): int {.inline.} =
  var res = x
  while res < y:
    yield res
    inc(res)
iterator range(x: int): int {.inline.} =
  var res = 0
  while res < x:
    yield res
    inc(res)
proc range(x, y: int): seq[int] {.inline.} =
  toSeq(x..y-1)
proc range(x: int): seq[int] {.inline.} =
  toSeq(0..x-1)
proc discardableId[T](x: T): T {.discardable.} =
  return x
template `:=`(x, y: untyped): untyped =
  when defined(x):
    (x = y; discardableId(x))
  else:
    (var x = y; discardableId(x))
when NimMajor <= 0 and NimMinor <= 17:
  proc count[T](co: openArray[T]; obj: T): int =
    for itm in items(co):
      if itm == obj:
        inc result
proc divmod(x, y: SomeInteger): (int, int) =
  (x div y, x mod y)
proc `min=`[T](x: var T; y: T): bool {.discardable.} =
  if x > y:
    x = y
    return true
  else:
    return false
proc `max=`[T](x: var T; y: T): bool {.discardable.} =
  if x < y:
    x = y
    return true
  else:
    return false

when NimMajor <= 0 and NimMinor <= 17:
  iterator pairs(n: NimNode): (int, NimNode) {.inline.} =
    for i in 0 ..< n.len:
      yield (i, n[i])

#[
when NimMajor <= 0 and NimMinor <= 18:
  macro parseInnerType(x: NimNode): untyped =
    newIdentNode("parse" & x[1][1].repr)
else:
  macro parseInnerType(x: typedesc): untyped =
    newIdentNode("parse" & x.getType[1][1].repr)
]#

proc parseInnerType(x: NimNode): NimNode =
  newIdentNode("parse" & x[1].repr)

proc inputAsTuple(ty: NimNode): NimNode =
  result = nnkStmtListExpr.newTree()
  t := genSym()
  result.add quote do: (let `t` = stdin.readLine.split)
  p := nnkPar.newTree()
  for i, typ_tmp in ty.pairs:
    var ece, typ: NimNode
    if typ_tmp.kind == nnkExprColonExpr:
      ece = nnkExprColonExpr.newTree(typ_tmp[0])
      typ = typ_tmp[1]
    else:
      ece = nnkExprColonExpr.newTree(ident("f" & $i))
      typ = typ_tmp
    if typ.repr == "string":
      ece.add quote do: `t`[`i`]
    else:
      parsefn := newIdentNode("parse" & typ.repr)
      ece.add quote do: `t`[`i`].`parsefn`
    p.add ece
  result.add p

macro inputAsType(ty: untyped): untyped =
  if ty.kind == nnkBracketExpr:
    if ty[0].repr == "string":
      return quote do: stdin.readLine.split
    else:
      parsefn := parseInnerType(ty)
      return quote do: stdin.readLine.split.map(`parsefn`)
      #[
        when NimMajor <= 0 and NimMinor <= 18:
          stdin.readLine.split.map(parseInnerType(ty.getType))
        else:
          stdin.readLine.split.map(parseInnerType(ty))
      ]#
  elif ty.kind == nnkPar:
    return inputAsTuple(ty)
  elif ty.repr == "string":
    return quote do: stdin.readLine
  else:
    parsefn := ident("parse" & ty.repr)
    return quote do: stdin.readLine.`parsefn`

macro input(query: untyped): untyped =
  doAssert query.kind == nnkStmtList
  result = nnkStmtList.newTree()
  letSect := nnkLetSection.newTree()
  for defs in query:
    if defs[0].kind == nnkIdent:
      tmp := nnkIdentDefs.newTree(defs[0], newEmptyNode())
      typ := defs[1][0]
      var val: NimNode
      if typ.len <= 2:
        val = quote do: inputAsType(`typ`)
      else:
        op := typ[2]
        typ.del(2, 1)
        val = quote do: inputAsType(`typ`).mapIt(`op`)
      if defs[1].len > 1:
        op := defs[1][1]
        it := ident"it"
        tmp.add quote do:
          block:
            var `it` = `val`
            `op`
      else:
        tmp.add val
      letSect.add tmp
    elif defs[0].kind == nnkPar:
      vt := nnkVarTuple.newTree()
      for id in defs[0]:
        vt.add id
      vt.add newEmptyNode()
      sle := nnkStmtListExpr.newTree()
      t := genSym()
      sle.add quote do: (let `t` = stdin.readLine.split)
      p := nnkPar.newTree()
      if defs[1][0].kind == nnkPar:
        for i, typ in defs[1][0].pairs:
          if typ.repr == "string":
            p.add quote do: `t`[`i`]
          else:
            parsefn := newIdentNode("parse" & typ.repr)
            p.add quote do: `t`[`i`].`parsefn`
      else:
        typ := defs[1][0]
        if typ.repr == "string":
          for i in 0..<defs[0].len:
            p.add quote do: `t`[`i`]
        else:
          parsefn := newIdentNode("parse" & typ.repr)
          for i in 0..<defs[0].len:
            p.add quote do: `t`[`i`].`parsefn`
      sle.add p
      vt.add sle
      letSect.add vt
    elif defs[0].kind == nnkBracketExpr:
      ids := nnkIdentDefs.newTree(defs[0][0], newEmptyNode())
      cnt := defs[0][1]
      typ := defs[1][0]
      var input: NimNode
      if typ.kind == nnkBracketExpr and typ.len > 2:
        op := typ[2]
        typ.del(2, 1)
        input = quote do: inputAsType(`typ`).mapIt(`op`)
      else:
        input = quote do: inputAsType(`typ`)
      var val: NimNode
      if defs[0].len > 2:
        op := defs[0][2]
        it := ident"it"
        val = quote do:
          block:
            var `it` = `input`
            `op`
      else:
        val = input
      if defs[1].len > 1:
        op := defs[1][1]
        it := ident"it"
        ids.add(quote do:
          block:
            var `it` = newSeqWith(`cnt`, `val`)
            `op`)
      else:
        ids.add(quote do: newSeqWith(`cnt`, `val`))
      letSect.add ids
  result.add letSect

#=== Template_Base =========================== }}}
#=== Template_PriorityQueue (HeapQueue) ====== {{{

#
#
#            Nim's Runtime Library
#        (c) Copyright 2016 Yuriy Glukhov
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.

##[
  The `heapqueue` module implements a
  `heap data structure<https://en.wikipedia.org/wiki/Heap_(data_structure)>`_
  that can be used as a
  `priority queue<https://en.wikipedia.org/wiki/Priority_queue>`_.
  Heaps are arrays for which `a[k] <= a[2*k+1]` and `a[k] <= a[2*k+2]` for
  all `k`, counting elements from 0. The interesting property of a heap is that
  `a[0]` is always its smallest element.

  Basic usage
  -----------
  .. code-block:: Nim
    import heapqueue

    var heap = initHeapQueue[int]()
    heap.push(8)
    heap.push(2)
    heap.push(5)
    # The first element is the lowest element
    assert heap[0] == 2
    # Remove and return the lowest element
    assert heap.pop() == 2
    # The lowest element remaining is 5
    assert heap[0] == 5

  Usage with custom object
  ------------------------
  To use a `HeapQueue` with a custom object, the `<` operator must be
  implemented.

  .. code-block:: Nim
    import heapqueue

    type Job = object
      priority: int

    proc `<`(a, b: Job): bool = a.priority < b.priority

    var jobs = initHeapQueue[Job]()
    jobs.push(Job(priority: 1))
    jobs.push(Job(priority: 2))

    assert jobs[0].priority == 1
]##

type HeapQueue*[T] = object
  ## A heap queue, commonly known as a priority queue.
  data: seq[T]

proc initHeapQueue*[T](): HeapQueue[T] =
  ## Create a new empty heap.
  HeapQueue[T](data: @[])

proc len*[T](heap: HeapQueue[T]): int {.inline.} =
  ## Return the number of elements of `heap`.
  heap.data.len

proc `[]`*[T](heap: HeapQueue[T]; i: Natural): T {.inline.} =
  ## Access the i-th element of `heap`.
  heap.data[i]

proc heapCmp[T](x, y: T): bool {.inline.} =
  return (x < y)

proc siftdown[T](heap: var HeapQueue[T]; startpos, p: int) =
  ## 'heap' is a heap at all indices >= startpos, except possibly for pos.  pos
  ## is the index of a leaf with a possibly out-of-order value.  Restore the
  ## heap invariant.
  var pos = p
  var newitem = heap[pos]
  # Follow the path to the root, moving parents down until finding a place
  # newitem fits.
  while pos > startpos:
    let parentpos = (pos - 1) shr 1
    let parent = heap[parentpos]
    if heapCmp(newitem, parent):
      heap.data[pos] = parent
      pos = parentpos
    else:
      break
  heap.data[pos] = newitem

proc siftup[T](heap: var HeapQueue[T]; p: int) =
  let endpos = len(heap)
  var pos = p
  let startpos = pos
  let newitem = heap[pos]
  # Bubble up the smaller child until hitting a leaf.
  var childpos = 2*pos + 1 # leftmost child position
  while childpos < endpos:
    # Set childpos to index of smaller child.
    let rightpos = childpos + 1
    if rightpos < endpos and not heapCmp(heap[childpos], heap[rightpos]):
      childpos = rightpos
    # Move the smaller child up.
    heap.data[pos] = heap[childpos]
    pos = childpos
    childpos = 2*pos + 1
  # The leaf at pos is empty now.  Put newitem there, and bubble it up
  # to its final resting place (by sifting its parents down).
  heap.data[pos] = newitem
  siftdown(heap, startpos, pos)

proc push*[T](heap: var HeapQueue[T]; item: T) =
  ## Push `item` onto heap, maintaining the heap invariant.
  heap.data.add(item)
  siftdown(heap, 0, len(heap)-1)

proc pop*[T](heap: var HeapQueue[T]): T =
  ## Pop and return the smallest item from `heap`,
  ## maintaining the heap invariant.
  let lastelt = heap.data.pop()
  if heap.len > 0:
    result = heap[0]
    heap.data[0] = lastelt
    siftup(heap, 0)
  else:
    result = lastelt

proc del*[T](heap: var HeapQueue[T]; index: Natural) =
  ## Removes the element at `index` from `heap`, maintaining the heap invariant.
  swap(heap.data[^1], heap.data[index])
  let newLen = heap.len - 1
  heap.data.setLen(newLen)
  if index < newLen:
    heap.siftup(index)

proc replace*[T](heap: var HeapQueue[T]; item: T): T =
  ## Pop and return the current smallest value, and add the new item.
  ## This is more efficient than pop() followed by push(), and can be
  ## more appropriate when using a fixed-size heap. Note that the value
  ## returned may be larger than item! That constrains reasonable uses of
  ## this routine unless written as part of a conditional replacement:
  ##
  ## .. code-block:: nim
  ##    if item > heap[0]:
  ##        item = replace(heap, item)
  result = heap[0]
  heap.data[0] = item
  siftup(heap, 0)

proc pushpop*[T](heap: var HeapQueue[T]; item: T): T =
  ## Fast version of a push followed by a pop.
  if heap.len > 0 and heapCmp(heap[0], item):
    swap(item, heap[0])
    siftup(heap, 0)
  return item

proc clear*[T](heap: var HeapQueue[T]) =
  ## Remove all elements from `heap`, making it empty.
  heap.data.setLen(0)

proc `$`*[T](heap: HeapQueue[T]): string =
  ## Turn a heap into its string representation.
  result = "["
  for x in heap.data:
    if result.len > 1: result.add(", ")
    result.addQuoted(x)
  result.add("]")

proc newHeapQueue*[T](): HeapQueue[T] =
  initHeapQueue[T]()

proc newHeapQueue*[T](heap: var HeapQueue[T]) =
  heap.clear()

#=== Template_PriorityQueue (HeapQueue) ====== }}}


input:
  (N, M): int
  Q[M]: (l: int, r: int, c: int)

proc `<`(x, y: (int, int)): bool =
  x[1] < y[1]

var
  node = newSeqWith(N, int.high)
  edge = newSeqWith(N, newSeq[(int, int)](0))
  hq = initHeapQueue[(int, int)]()
  locked = newSeq[bool](N)

for l, r, c in Q.items:
  edge[l-1].add((r-1, c))
  for i in range(l, r):
    edge[r-1].add((i, 0))

node[0] = 0
hq.push((0, 0))

while hq.len > 0 and locked.anyIt(not it):
  let (v, l) = hq.pop
  if locked[v]: continue
  locked[v] = true
  for w, c in edge[v].items:
    if locked[w] or node[w] <= l+c: continue
    node[w] = l+c
    hq.push((w, l+c))

if node[N-1] == int.high:
  echo -1
else:
  echo node[N-1]
