Мирлин Теренс тщетно пытался спасти Рика и Валлону от агентов Трантора. Переодевшись патрульным, он разыскивал их по всему Верхнему городу, однако никак не мог напасть на их след. Встреча произошла уже недалеко и космопорта, но тут завязалась перестрелка между Теренсом и агентом, а Рик и Валлона, не узнав Мирлина, сбежали, и уже летели на космическом корабле до Сарка. Теренс понимал, что не может лететь вслед за ними на корабле — его тут же узнают. Однако у многих зажиточных граждан Верхнего города были космические яхты, путешествие на которой вызвало бы намного меньше подозрений. Конечно, Теренс к этим гражданам не относился и ключей от яхты не имел, но форма патрульного, оружие и полумрак ночных улиц помогли их раздобыть.
Теренс все еще должен был оставаться незамеченным, и потому ему стоило избегать встречи с патрульными. Квартал рядом с портом состоит из $n$ перекрестков, соединенных $m$ дорожками с односторонним движением, для каждой дорожки известно, за какое время ее можно преодолеть. Посреди ночи по кварталу ходили всего двое патрульных, которые сейчас находятся на перекрестках $s_1$ и $s_2$. По рации, отобранной у патрульного, Теренс узнал, что они должны обойти $k$ перекрестков $p_1, p_2,... p_k$ в заданном порядке (один перекресток может встречаться в этом списке несколько раз). Обходить они будут по одному, то есть на каждом из заданных перекрестков может побывать один из патрульных. Они действуют следующим образом: сначала какой-либо из патрульных доходит до перекрестка $p_1$ и сообщает об этом напарнику. После этого какой-либо патрульный начинает свое движение до перекрестка $p_2$. Так происходит, пока патрульные не осмотрят перекресток $p_k$, после чего их смена заканчивается. Если в какой-то момент патрульным необходимо проверить перекресток $i$, и какой-то из патрульных как раз находится на этом перекрестке, они переходят к проверке следующего перекрестка. При необходимости патрульные могут находиться на одном перекрестке. Патрульные хотят как можно быстрее закончить свою работу, а потому выбирают пути и разделяют между собой перекрестки таким образом, чтобы обход занял минимальное время.
Мирлин Теренс решил, что проще всего проникнуть в порт во время смены патрульных. Поэтому он спрашивает вас: сколько времени патрульные будут совершать обход, если они выбирают свои пути оптимально?
В первой строке записаны три числа: $n, m$ и $k$ $(1 <= n <= 300, 0 <= m <= n dot.op (n -1), 1 <= k <= 1000)$ — количество перекрестков, дорожек и количество перекрестков, которые должны осмотреть патрульные, соответственно.
В следующих $m$ строках через пробел записаны по три числа: $v_i, u_i$ и $t_i$ $(1 <= v_i, u_i <= n, 1 <= t_i <= 10^6)$, означающие, что от перекрестка с номером $v_i$ идет дорожка к перекрестку с номером $u_i$, по которой можно пройти за время $t_i$.
В следующей строке через пробел записаны номера перекрестков $p_1, p_2, \\dots p_k$.
В последней строке через пробел записаны два числа — $s_1$ и $s_2$.
Выведите одно число — время обхода патрульных, либо число $-1$, если патрульные не смогут обойти перекрестки в заданном порядке.
В первом примере между перекрестками нет ни одной дорожки, но патрульные находятся на $5$-м и $4$-м перекрестках. Так как патрульным требуется проверить $5, 5, 4, 4$ и $5$ перекрестки, им остается лишь стоять на месте каждый раз. Таким образом, на перемещение время тратиться не будет.
Во втором примере оптимален следующий алгоритм. Первый патрульный перемещается с $1$-го перекрестка на $5$-й за $3$ единицы времени, а затем возвращается на $1$ перекресток за $10$ единиц времени. После этого второй патрульный, находясь на $2$-м перекрестке проверяет его и переходит на $3$-й перекресток за $2$ единицы времени. Таким образом, получаем суммарное время: $3 + 10 + 2 = 15$.
## Входные Данные
В первой строке записаны три числа: $n, m$ и $k$ $(1 <= n <= 300, 0 <= m <= n dot.op (n -1), 1 <= k <= 1000)$ — количество перекрестков, дорожек и количество перекрестков, которые должны осмотреть патрульные, соответственно.В следующих $m$ строках через пробел записаны по три числа: $v_i, u_i$ и $t_i$ $(1 <= v_i, u_i <= n, 1 <= t_i <= 10^6)$, означающие, что от перекрестка с номером $v_i$ идет дорожка к перекрестку с номером $u_i$, по которой можно пройти за время $t_i$.В следующей строке через пробел записаны номера перекрестков $p_1, p_2, \\dots p_k$.В последней строке через пробел записаны два числа — $s_1$ и $s_2$.
## Выходные Данные
Выведите одно число — время обхода патрульных, либо число $-1$, если патрульные не смогут обойти перекрестки в заданном порядке.
## Примеры
Входные данные5 0 5
5 5 4 4 5
5 4
Выходные данные0
Входные данные5 4 4
1 5 3
5 1 10
1 2 1
2 3 2
5 1 2 3
1 2
Выходные данные15
## Примечание
В первом примере между перекрестками нет ни одной дорожки, но патрульные находятся на $5$-м и $4$-м перекрестках. Так как патрульным требуется проверить $5, 5, 4, 4$ и $5$ перекрестки, им остается лишь стоять на месте каждый раз. Таким образом, на перемещение время тратиться не будет.Во втором примере оптимален следующий алгоритм. Первый патрульный перемещается с $1$-го перекрестка на $5$-й за $3$ единицы времени, а затем возвращается на $1$ перекресток за $10$ единиц времени. После этого второй патрульный, находясь на $2$-м перекрестке проверяет его и переходит на $3$-й перекресток за $2$ единицы времени. Таким образом, получаем суммарное время: $3 + 10 + 2 = 15$.
[samples]
**Definitions**
Let $ n, m, k \in \mathbb{Z}^+ $ denote the number of intersections, directed roads, and checkpoints respectively.
Let $ G = (V, E) $ be a directed graph with $ V = \{1, 2, \dots, n\} $ and $ E \subseteq V \times V $, where each edge $ (v_i, u_i) \in E $ has weight $ t_i \in \mathbb{Z}^+ $.
Let $ P = (p_1, p_2, \dots, p_k) \in V^k $ be the sequence of checkpoints to be visited in order.
Let $ s_1, s_2 \in V $ be the initial positions of the two patrols.
Let $ d(u, v) \in \mathbb{R}_{\geq 0} \cup \{\infty\} $ denote the shortest path distance from $ u $ to $ v $ in $ G $, computed via all-pairs shortest paths (e.g., Floyd-Warshall). If no path exists, $ d(u, v) = \infty $.
**Constraints**
1. $ 1 \leq n \leq 300 $
2. $ 0 \leq m \leq n(n-1) $
3. $ 1 \leq k \leq 1000 $
4. $ 1 \leq t_i \leq 10^6 $
5. For all $ i \in \{1, \dots, k\} $, $ p_i \in V $
6. $ s_1, s_2 \in V $
**Objective**
Compute the minimum total time required for two patrols to visit checkpoints $ p_1, p_2, \dots, p_k $ in order, such that:
- At step $ j \in \{1, \dots, k\} $, **exactly one** patrol moves from its current position to $ p_j $.
- If a patrol is already at $ p_j $, no movement is needed (time cost = 0).
- Patrols may occupy the same intersection.
- The goal is to minimize the sum of movement times over all steps.
Define $ \text{dp}[j][a][b] $ as the minimum time to have completed visiting the first $ j $ checkpoints, with patrol 1 at position $ a \in V $ and patrol 2 at position $ b \in V $.
Initialize:
$ \text{dp}[0][s_1][s_2] = 0 $, and all other $ \text{dp}[0][a][b] = \infty $.
Transition:
For each $ j \in \{1, \dots, k\} $, and for all $ a, b \in V $:
$$
\text{dp}[j][p_j][b] = \min_{a' \in V} \left( \text{dp}[j-1][a'][b] + d(a', p_j) \right) \\
\text{dp}[j][a][p_j] = \min_{b' \in V} \left( \text{dp}[j-1][a][b'] + d(b', p_j) \right)
$$
(If $ p_j = a $, then $ d(a, p_j) = 0 $; same for $ b $.)
Final answer:
$$
\min_{a, b \in V} \text{dp}[k][a][b]
$$
If the minimum is $ \infty $, output $ -1 $.