## TL;DR

Given a number of vertices `N` and a list of weighted directed edges in a directed acyclic graph (each edge is written as `[start, end, weight]` where `from < to`), compute the weight of the shortest path from vertex `0` to vertex `N - 1`.  If there is no such path, return `-1`.

## Background

A weighted DAG is a directed acyclic graph where each edge has a weight associated with it:













1
5
3
1
5




A
B
C
D


In this example, the shortest path from A to D is given by A -> B -> D, which has a total weight of 4.

Finding shortest distances in DAGs is made easier by the fact that the nodes can be _linearized:_ they can be given an order `A1, A2, ..., An` such that edges only point forward (that is, there are no edges from `Aj` to `Ai` when `j > i`).  In the example above, the two possible linear orderings are `A, B, C, D` and `A, C, B, D.`














1

1
5
5
3





A
B
C
D


## Your Task

Given a number `N` (indicating a graph with vertices `0, 1, ..., N-1`) and a list of weighted edges `[start, end, weight]` for a DAG, where `start < end` for each edge, find the weight (a.k.a. length) of the shortest path from node `0` to node `N-1`.

For example, if the input is

```
N = 4
edgeList = [
  [0, 1, 1], [0, 2, 5], [0, 3, 5], [1, 3, 3], [2, 3, 1]
]
```

then we have the graph depicted above (with `0 = A`, `1 = B`, etc.) and the answer is `4`.

If there is no path from node `0` to node `N-1`, return `-1`.

## Notes and Warnings

**Precondition:** `N` will always be greater than 1, and edge weights will always be positive integers.  There may be multiple edges going between two nodes.

**Warning:** You will probably need to use a dynamic programming solution if you want your solution to run fast enough not to time out--that's the whole point of this kata!


However, a well-written general shortest-path algorithm such as Dijkstra's Algorithm may also be fast enough to past the soak tests.  (The reason is that the dividing line between linear and linearithmic time is hard to define and depends on a variety of external factors, so the kata's tests err on the safe side.)

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def shortest(N, edgeList):\n    import math\n    edgeList.sort(key=lambda x: x[0])\n    path_length = [math.inf for _ in range(N)]\n    path_length[0] = 0\n        \n    for start, end, weight in edgeList:\n#         each edge is written as [start, end, weight] where from < to więc to działa, \n#         ale gdyby taki warunek nie był prawdziwy to np.\n#         shortest(5, [(0,2,0), (0,3,1), (2,1,0), (3,4,1), (1,4,0)]) zwracałoby 2, zamiast 0\n        if path_length[start] == math.inf:\n            continue\n        path_length[end] = min(path_length[start] + weight, path_length[end])\n    \n    result = path_length[N-1]\n    return result if result is not math.inf else -1\n\n\n\n\n\n# def shortest(N, edgeList):\n#     import math, heapq, collections\n#     edges = collections.defaultdict(lambda:collections.defaultdict(lambda:math.inf))\n#     path_length = [math.inf for _ in range(N)]\n#     path_length[0] = 0\n#     for start, end, weight in edgeList:\n#         edges[start][end] = min(weight, edges[start][end])\n#     h = [(0,0)]\n#     visited = set()\n#     heapq.heapify(h)\n#     while h:\n#         sum, start = heapq.heappop(h)\n#         if start == N-1: return sum\n#         if start in visited: continue\n#         for end, weight in edges[start].items():\n#             if end in visited: continue\n#             if sum + weight < path_length[end]:\n#                 path_length[end] = sum + weight\n#                 heapq.heappush(h, (sum+weight, end))\n#         visited.add(start)\n#     return -1\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'shortest'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 5656