Біг підтюпцем

Фібі дізналася, що фізичні вправи значно покращують як фізичне, так і психічне здоров'я. Вона ніколи раніше не займалася бігом підтюпцем і вирішила спробувати. Проте, вона знає, що швидко втратить інтерес, якщо доведеться постійно повторювати одне й те саме. Щоб виробити звичку бігати підтюпцем, Фібі вирішила прийняти виклик: вона буде виходити на пробіжку кожного вечора, поки знаходить новий цікавий маршрут. Для неї маршрут вважається цікавим, якщо він проходить по вулиці, якою вона ще не бігала. Фібі просить вас допомогти визначити, скільки днів вона зможе виходити на пробіжку, якщо ретельно спланує свої маршрути.

Фібі надає вам опис свого району. Вона живе на перехресті і описує всі перехрестя в окрузі. Вона також повідомляє, які перехрестя з'єднані вулицями, і яка довжина кожної вулиці в метрах. Кожна вулиця з'єднує два різні перехрестя. Жодні дві різні вулиці не з'єднують одні й ті самі два перехрестя. Крім того, ви можете припустити, що Фібі описує лише ті вулиці, до яких можна дістатися з її дому, і що вулиці можна пройти в обох напрямках, оскільки Фібі ходить пішки.

Пробіжка починається і закінчується в домі Фібі, і довжина маршруту повинна бути в межах діапазону, вказаного Фібі. Коли Фібі виходить на вулицю, вона не зобов'язана проходити всю вулицю (їй дозволено розвернутися в будь-якій точці), але навіть якщо вона це зробить, це буде вважатися, як якщо б вона побачила всю вулицю для цілей визначення, чи цікаві пробіжки. Пробіжка вважається цікавою, якщо вона включає в себе вулицю (або її частину), яка не з'являлася в попередніх пробіжках. Досягнення перехрестя не вважається відвідуванням усіх прилеглих до нього вулиць.

Вхідні дані

Починається з одного рядка, що містить чотири цілі числа $ISLU$. $I(1\le I\le 10^5)$ представляє кількість перехресть у окрузі, а $S(0\le S\le 10^5)$ представляє кількість вулиць. $L$ — мінімальна кількість метрів у допустимій пробіжці, а $U(1\le L\le U\le 42195$, Фібі не буде бігти більше ніж марафонську дистанцію) — це максимальна кількість метрів у допустимій пробіжці.

Далі йде $S$ рядків, кожен з яких відповідає вулиці. Кожен такий рядок містить $3$ цілі числа $ijl$. $i$ та $j$ — це перехрестя, які з'єднує вулиця, а $l(1\le l\le 1000)$ — довжина вулиці в метрах. Перехрестя пронумеровані від $0$ до $I-1$, так що Фібі живе на перехресті з номером $0$.

Вихідні дані

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

Приклади

Примітка

Ось приклад цікавого $3$-денного плану пробіжок для першого прикладу:

• У перший день бігайте туди-сюди по вулиці між $0$ і $1(80$ метрів).

• На другий день пробігти $40$ метрів по вулиці до $2$, після чого повернутися тим же шляхом ($80$ метрів).

• На третій день бігти по вулиці до $1$, потім пробігти $5$ метрів у напрямку $2$, потім повернутися назад тим же шляхом ($90$ метрів).

Ось одна з можливих пробіжок: бігти від $0$ до $1$, потім назад до $0$, потім півметра в напрямку $1$, а потім назад до $0$.