Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×
E. Кратчайший путь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан неориентированный взвешенный граф, состоящий из $$$n$$$ вершин и $$$m$$$ рёбер. Вершины графа пронумерованы целыми числами от $$$1$$$ до $$$n$$$. В вершине $$$i$$$ записано целое число $$$a_i$$$, а у каждого ребра графа есть стоимость.

Путь — это последовательность попарно-различных вершин, где любые две последовательные вершины соединены ребром. Стоимость пути определяется как сумма стоимостей всех рёбер на этом пути.

Определим красоту пути, состоящего из вершин $$$v_1, v_2, \dots, v_c$$$, как сумму $$$a_{v_1} + a_{v_2} + \cdots + a_{v_c}$$$ чисел, записанных в его вершинах. Назовём путь красивым, если его красота делится на $$$k$$$ без остатка.

Ваша задача — найти красивый путь с наименьшей возможной стоимостью или сообщить, что красивых путей не существует.

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n \le 10\,000$$$; $$$1\le m \le 10\,000$$$; $$$2 \le k \le 6$$$) — количество вершин в графе, количество рёбер в графе и необходимый делитель красоты пути соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \lt a_i \lt k$$$) — числа, записанные в вершинах.

Затем следуют $$$m$$$ строк, $$$i$$$-я из них содержит три целых числа $$$x_i$$$, $$$y_i$$$ и $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$; $$$1 \le w_i \le 10^9$$$), означающих, что $$$i$$$-е ребро графа соединяет вершины $$$x_i$$$ и $$$y_i$$$ и имеет стоимость $$$w_i$$$.

Гарантируется, что заданный граф не содержит петель или кратных рёбер.

Выходные данные

В единственной строке выведите единственное целое число — минимально возможную стоимость красивого пути, или -1, если красивых путей в заданном графе не существует.

Примеры
Входные данные
4 4 3
1 1 2 1
1 2 1
2 3 4
4 3 5
4 1 1
Выходные данные
2
Входные данные
2 1 4
2 3
1 2 1
Выходные данные
-1