Задача: Vacation Planning

Air Bovinia планирует соединить N ферм (1 <= N <= 200), в которых живут
коровы. K из этих ферм выбраны как хабы (1 <= K <= 100, K <= N).
Фермы пронумерованы от 1 до N, при этом фермы 1..K являются хабами.

Сейчас имеется M (1 <= M <= 10,000) однонаправленных полётов.
Полёт I происходит из фермы u_i в ферму v_i, с ценой d_i долларов
(1 <= d_i <= 1,000,000).

Авиакомпания получила требование на Q (1 <= Q <= 10,000)
однонаправленных путешествий. I-ое путешествие из фермы a_i в ферму b_i.
Путешествие может включать любую последовательность прямых перелётов,
(возможно даже посещая одну и туже ферму несколько раз),
но эта последовательность должна включать как минимум один хаб
(который может быть а может и не быть в ферме старта или назначения).
Следствием последнего требования может быть отсутствие корректного
маршрута из a_i в b_i. Для всех остальных путешествий Ваша цель
помочь Air Bovinia определить минимальную стоимость корректного маршрута.

PROBLEM NAME: vacation

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

* Строка 1: Четыре целых числа: N, M, K, Q.

* Строки 2..1+M: Строка i+1 содержит u_i, v_i, d_i для полёта i.

* Строки 2+M..1+M+Q: Строка 1+M+i описывает i-ое путешествие в терминах a_i b_i

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

* Строка 1: Количество путешествий (из Q) для которых существует
корректный маршрут

* Строка 2: Сумма всех корректных минимальных маршрутов.

Примечание

Путешествие из 3 в 2 может быть осуществлено единственным способом
с ценой 10+7. путешествие из 2 в 3 невозможно, поскольку из 2 нет
ни одного полёта. Путешествие из 1 в 2 возможно единственным способом
с ценой 7.

Ваш ответ: