Shortest Paths
Дизайн и Анализ на Алгоритми, 2015
Time Limit: 0.7s, Memory Limit: 64MiB
Ели няма проблем с намирането на най-къс път дори наум. Алгоритъмът на Дейкстра за нея е като детска игра, но понякога ползването му на практика не е много адекватно. Например, само няколко месеца след като намери най-късия път между нейния дом и университета, той почна да ѝ доскучава. Оказва се, че има и други алтернативни пътища, които са със същата дължина, но ползват различни улици. Сега момичето се чуди колко на брой са те.

Градът, в който живее Ели, е зададен под формата на граф с N върха и M насочени ребра между тях (Fi, Ti, Pi), указващи улица от връх Fi до връх Ti, с дължина Pi. Считаме, че къщата на Ели е върхът с индекс 1, а университетът – този с индекс N.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и M – броят върхове и ребра в графа. На следващите M реда ще има по една тройка числа Fi, Ti, Pi, задаващи по едно насочено ребро с неговото тегло. Възможно е да има повече от едно ребро между двойка върхове, както е и възможно да има ребро от връх до себе си.
Изход
На стандартния изход изведете разделени с шпация две цели числа – дължината на минималния път и броя различни начини, по които може да бъде постигнат. Два пътя се считат за различни ако ползват поне едно различно ребро. Тъй като броят пътища може да е много голям, изведете само неговия остатък при деление на 1,000,000,007. В случай, че няма път между 1 и N, като цена изведете "-1", а като брой пътища - "0".
Ограничения
  • 2 ≤ N ≤ 100,000
  • 1 ≤ M ≤ 500,000
  • 1 ≤ Pi ≤ 1,000,000,000
  • 1 ≤ Fi, TiN
Примерен Вход Примерен Изход
5 6 1 2 10 1 4 29 2 3 50 4 3 13 4 5 24 3 5 11 53 2
3 1 1 2 13 -1 0
В първия пример има общо три пътя: (1, 2, 3, 5) с цена 71, (1, 4, 3, 5) с цена 53, и (1, 4, 5) с цена 53. Последните два са тези с минимална цена. Във втория пример няма път между началния и крайния връх, съответно броят пътища (респективно най-къси такива) е нула.
Мрън!