2180: Air path
Перегляд у форматі PDFКомпанія Air Glob планує з'єднати повітряним сполученням ~N~ міст країни. Аеропорти перенумеровані від 1 до ~N~ і у перших ~K~ аеропортах можливі пересадки. На даний момент є ~M~ однонаправлених маршрутів. Політ ~i~ відбувається з аеропорту ~U_i~ до ~V_i~ з ціною ~D_i~ у.о.
Авіакомпанія отримала замовлення на ~Q~ подорожей. Подорож ~i~ з аеропорту ~A_i~ до ~B_i~ може складатися із довільної кількості прямих перельотів, (навіть можливий варіант із відвідуванням одного із аеропортів декілька разів) але є обов'язковим відвідування хоча би одного аеропорту з пересадкою, який може бути не стартовим і не кінцевим. Отже, не гарантується, що є коректним маршрут від ~A_i~ до ~B_i~.
Завдання: необхідно знайти мінімальну вартість подорожей для всіх коректних маршрутів.
Input
Перший рядок містить чотири цілих числа: ~N~, ~M~, ~K~, ~Q~ (~1 \le N \le 200, 1 \le K \le 100, 1 \le M,Q \le 10000~). Рядки від 2 до ~M+1~: ~U_i~, ~V_i~, ~D_i~ (~1 \le D_i \le 1000000~).
Наступні ~Q~ рядків містять варіанти подорожей ~A_i~, ~B_i~.
Output
У першому рядку вивести кількість коректних маршрутів, а в другому - їх мінімальну вартість.
Scoring
Кожен тест оцінюється окремо
Sample Input 1
3 3 1 3
3 1 10
1 3 10
1 2 7
3 2
2 3
1 2
Sample Output 1
2
24
Notes
Подорож із 3 в 2 можна здійснити єдиним способом із вартістю 10+7. Маршрут із 2 в 3 є некоректним. Політ із 1 в 2 можливий і його вартість рівна 7.
Коментарі
То всі аеропорти на шляху між a i b окрім самих a i b мають бути з пересадкою?