E. Выпавшие мешки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Игорь и Ира позвали к себе в гости Сашу и Лешу, чтобы поиграть в настольные игры. На сегодняшний вечер была выбрана игра «Орлеан».

В игре «Орлеан» игроки могут передвигаться из одного города в другой город по дорогам. По каждой дороге каждый игрок может ходить по нескольку раз.

По легенде игры "Орлеан" перед началом игры на каждой дороге было оставлено по одному мешку с ресурсом от торговца. Каждый ресурс имеет свою ценность в победных очках, например, стог сена стоит 1 победное очко, а шелковая ткань целых 5 очков. Игрок, проходя по дороге, может забрать ресурс, если он еще лежит в мешке.

Под конец игры Игорь находится в городе под номером 1 и планирует сделать ровно $$$k$$$ ходов по дорогам, собирая как можно больше победных очков. Достоверно известно, что Ира, Саша и Леша не планируют тратить последние свои действия в игре на передвижения по дорогам, а также известна карта дорог со всеми оставшимися ресурсами и их ценностью.

Помогите Игорю посчитать, какое максимальное количество очков Игорь сможет собрать, бегая по дорогам.

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

В первой строке задано три целых числа $$$n$$$, $$$m$$$, $$$k$$$ $$$(1\leq n\leq 10^4,1\leq m\leq 10^4,1 \leq k \leq 6)$$$  — количество городов на карте, количество дорог соединяющих города, количество ходов, которое планирует сделать Игорь.

Далее в $$$m$$$ строках записаны три целых числа $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ $$$(1\leq a_i\leq n,1\leq b_i \leq n,0 \leq c_i \leq 10)$$$  — номера городов, между которыми проходит дорога, и ценность ресурса лежащего в мешке, если $$$c_i$$$ равняется нулю это означает, что кто-то уже взял данный ресурс в мешке и мешок пуст.

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

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

Выведите одно целое число  — максимальное количество очков, которое может получить Игорь, собирая ресурсы на дорогах.

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