Ограничения: время – 750ms/1500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Карета Золушки может ехать не только по обычным дорогам, но и волшебными путями.
Хотя движение по волшебному пути для путешественника происходит в мгновение ока, в реальном мире проходит `x` минут
(независимо от расстояния между начальной и конечной точкой перемещения). Значение `x` целым положительным числом,
и неизвестно Золушке, так как она впервые едет на волшебной карете.
Известна информация о населенных пунктам в королевстве, времени перемещения между пунктами по обычным дорогам и волшебных путях,
которые существуют между некоторыми пунктами. И обычные дороги, и волшебные пути являются односторонними.
Напишите программу, которая проанализирует все возможные способы перемещения между пунктами `A` и `B` и найдет время кратчайшего пути
для всех возможных значений `x`.
Первая строка ввода содержит два целых числа -- количество населенных пунктов `N` (`2<=N<=500`) и количество дорог (обычных и волшебных) между ними
`M` (`1<=M<=10000`). Далее следует `M` строк, описывающих дороги, сначала два целых числа `a_i` и `b_i` (`1<=a_i,b_i<=N, a_i!=b_i`) -- номера
населенных пунктов, которые связывает односторонняя дорога, затем символ ``x`` для волшебной дороги или целое число `t_i` (`1<=t_i<=10^6`) --
время в минутах для перемещения по обычной дороге.
Следующая строка содержит одно целое число `Q` (`1 <= Q <=10`) -- количество запросов на получение информации. Далее следует `Q` строк, каждая строка
содержит два целых числа `A_j` и `B_j` (`1<=A_j,B_j<=N, A_j!=B_j`) -- номера
населенных пунктов, между которыми нужно найти все возможные варианты времени кратчайшего пути.
Для каждого запроса вывести два целых числа -- количество возможных вариантов для времени кратчайшего пути из пункта `A_j` в пункт `B_j`
и сумму этих вариантов. Если проезд из пункта `A_j` в пункт `B_j` невозможен, то вывести 0 для количества вариантов и 0 для суммы. Если существует неограниченное количество вариантов -- вывести строку, содержащую ``inf`` (см. пример).
```sample Пример ввода 1
4 4
1 2 x
2 3 x
3 4 x
1 4 8
3
2 1
1 3
1 4
```
```sample Пример вывода 1
0 0
inf
3 17
```
Граф дорог для примера 1:
Есть 3 варианта для времени кратчайшего пути из пункта 1 в пункт 4: 3 для `x=1`, 6 для `x=2` и 8 для `x>=3`, в сумме 3+6+8=17.
```sample Пример ввода 2
3 5
3 2 x
2 1 x
2 1 5
1 3 10
3 1 20
6
1 2
2 3
3 1
2 1
3 2
1 3
```
```sample Пример вывода 2
inf
5 65
15 185
5 15
inf
1 10
```
Граф дорог для примера 2:
В 50% тестов `N <= 30`, `M <= 300`, `t_i <= 50`.
Начало
Рабочее место участника
Графы