K. Длиннейший путь в ациклическом графе

Дан ориентированный ациклический граф с весами любого знака. Найдите наибольший вес пути из вершины 1 в вершину $n$.

В общем графе длиннейший путь искать бесполезно: задача NP-полна, а с положительными циклами ответа просто нет. В ациклическом — считается за $O(n + m)$.

Приём: топологическая сортировка плюс динамика. Перебираем вершины в топологическом порядке; к моменту, когда очередь доходит до $v$, все входящие в неё рёбра уже обработаны:

Вершины, недостижимые из первой, в переборе не участвуют — иначе они внесут в максимум мусор.

Это тот же приём, что мы применяли к конденсации во втором занятии по обходу в глубину, и он же — основа динамики по ациклическому графу вообще. Форда — Беллмана тут не нужно: ациклический граф разбирается быстрее.

Первая строка содержит числа $n$ ($1 \le n \le 10^5$) и $m$ ($0 \le m \le 2 \cdot 10^5$).

Далее идут $m$ строк с рёбрами: начало, конец и вес ($-10^4 \le w \le 10^4$). Граф ациклический; возможны кратные рёбра.

Одно число — наибольший вес пути из 1 в $n$, или $-1$, если пути нет.