EduBrick

K. Сколько рёбер в длиннейшем пути

3000 мс · 256 МБ · всё или ничего

Как классная задача K, но выведите вес длиннейшего пути и количество рёбер в нём. Если путей наибольшего веса несколько, возьмите тот, где рёбер меньше всего.

Формат ввода

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

Далее идут mm строк с рёбрами: начало, конец и вес (−104≤w≤104-10^4 \le w \le 10^4). Граф ациклический.

Формат вывода

Два числа: вес длиннейшего пути из 1 в nn и количество рёбер, или −1-1, если пути нет.

Примеры

ввод
4 5
1 2 5
2 4 5
1 3 1
3 4 1
1 4 10
вывод
10 1
ввод
2 0
вывод
-1
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.