Когда Незнайка ходит в гости к своим друзьям, он либо идет пешком, либо едет на такси. Всё зависит от расстояния.
Если предстоит пройти без отдыха не более $$$D$$$ километров, Незнайка идет пешком, а иначе — берёт такси.
В свой день рождения Незнайка решил навестить всех своих друзей. Но самое главное — он хочет минимизировать число своих поездок на такси!
Чтобы добиться этого, ему, возможно, придётся неоднократно заходить к кому-то из друзей, чтобы отдохнуть, и, возможно, также для отдыха неоднократно возвращаться к себе домой. После захода в любой дом Незнайка отдыхает, поэтому когда после этого он выходит на улицу, у него достаточно сил, чтобы пройти ещё $$$D$$$ километров.
Известно, что некоторые пары домов связаны двухсторонними дорогами, для каждой из которых известна её протяженность. Ходить пешком и ездить на такси можно только по этим дорогам. От любого дома можно добраться по дорогам до любого другого.
Любая поездка Незнайки на такси начинается и заканчивается возле одного из домов. Посещение друга возможно только после окончания поездки.
За одну поездку такси может проехать по любому количеству дорог. Например, Незнайка может захотеть за одну поездку проехать на такси по нескольким дорогам и не останавливаться в домах, которые встречаются ему по пути.
Требуется выяснить, какое минимальное количество поездок на такси может сделать Незнайка и при этом навестить всех своих друзей, если начать свой путь и закончить его Незнайка должен у себя дома?
В первой строке вводятся три целых числа $$$N$$$, $$$M$$$ и $$$D$$$, где $$$N$$$ — количество друзей у Незнайки $$$(1 \le N \le 10^5)$$$, $$$M$$$ — это количество дорог между домами $$$(N \le M \le \min(N\cdot(N+1)\ /\ 2,\ 2\cdot10^5))$$$, а $$$D$$$ — это максимальное расстояние, которое Незнайка готов пройти пешком без отдыха $$$(1 \le D \le 1\,000)$$$.
Далее идут $$$M$$$ строк, содержащих по три целых числа $$$h_1$$$, $$$h_2$$$ и $$$d_{h_1h_2}$$$, где $$$h_1$$$ и $$$h_2$$$ — номера домов, соединённых двухсторонней дорогой, $$$(1 \le h_1,\ h_2 \le N + 1,\ h_1 \neq h_2)$$$, а $$$d_{h_1h_2}$$$ — длина этой дороги $$$(1 \le d_{h_1h_2} \le 1\,000)$$$. Гарантируется, что между каждой парой домов существует не более одной дороги и что от любого дома можно добраться по дорогам до любого другого.
Незнайка живёт в доме с номером $$$1$$$.
Выведите одно целое число — минимальное количество поездок на такси, которое позволит Незнайке навестить всех своих друзей и вернуться обратно к себе домой.
Для каждой подгруппы баллы начисляются только в случае прохождения всех тестов в ней самой и во всех необходимых подгруппах.
| Подгруппа | Дополнительные ограничения | Баллы | Необходимые подзадачи |
| $$$0$$$ | Тесты из условия | $$$0$$$ | — |
| $$$1$$$ | $$$N \le 100$$$ | $$$50$$$ | 0 |
| $$$2$$$ | — | $$$50$$$ | 0, 1 |
2 3 51 2 41 3 32 3 6
0
6 8 31 2 31 3 22 3 14 5 14 6 25 6 31 7 74 7 9
3
Пояснение к примеру 1: один из возможных маршрутов без поездок на такси $$$1 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 1$$$.
Пояснение к примеру 2: один из возможных маршрутов с минимальным числом поездок на такси $$$1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 7 \rightarrow (4) \rightarrow 5 \rightarrow 6 \rightarrow 4 \rightarrow (7) \rightarrow 1$$$. В скобках указаны номера домов, мимо которых он проехал, пока передвигался на такси. Три поездки на такси: $$$1 \rightarrow 7$$$, $$$7 \rightarrow (4) \rightarrow 5$$$ и $$$4 \rightarrow (7) \rightarrow 1$$$.
| Name |
|---|