Игорь и Ира позвали к себе в гости Сашу и Лешу, чтобы поиграть в настольные игры. На сегодняшний вечер была выбрана игра «Орлеан».
В игре «Орлеан» игроки могут передвигаться из одного города в другой город по дорогам. По каждой дороге каждый игрок может ходить по нескольку раз.
По легенде игры "Орлеан" перед началом игры на каждой дороге было оставлено по одному мешку с ресурсом от торговца. Каждый ресурс имеет свою ценность в победных очках, например, стог сена стоит 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
