İnək kartinqi
Bessi və fermer Con keçi yarışlarından zövq alırlar. Bu yarışlar, başqalarının sevdiyi Go-Kart yarışlarına bənzəyir, lakin burada arabaları keçilər çəkir və yol yaxınlıqdakı kənd təsərrüfatı sahələrindən ibarətdir. Sahələr n çəmənlikdən və m yoldan ibarətdir, hər biri bir cüt çəmənliyi birləşdirir.
Bessi yaxınlıqdakı fermalarda dairəvi bir yol qurmaq istəyir. Ferma, iki və ya daha çox çəmənliyin alt qrupudur, burada hər çəmənlikdən digərinə unikal yol ardıcıllığı ilə çatmaq mümkündür.
Yaxınlıqdakı kənd təsərrüfatı sahələrində bir neçə ferma ola bilər. Tutaq ki, artıq k ferma mövcuddur. Bessi bütün k fermaları birləşdirərək, uzunluğu x olan k yol əlavə edərək karting üçün bir dairə yaratmaq istərdi. Hər bir fermaya dəqiq bir dəfə baş çəkmək lazımdır və hər bir fermada ən azı bir yoldan keçmək lazımdır.
Yol yarışçılar üçün maraqlı olması üçün onun ümumi uzunluğu ən azı y olmalıdır. Bessi bütün belə maraqlı yolların uzunluqlarının cəmini bilmək istəyir. Bir yol digərindən fərqlənir, əgər bir yolda iki qonşu çəmənlik (fermalar arasında yollar əlavə edildikdən sonra) var, amma digərində yoxdur. Qeyd edək ki, yalnız seçilmiş yollar əhəmiyyətlidir, keçilərin hansı istiqamətdə hərəkət edəcəyi deyil.
Giriş Məlumatları
Birinci sətir n, m, x və y ədədlərini ehtiva edir (1 ≤ n ≤ 1500, 1 ≤ m ≤ n − 1, 0 ≤ x, y ≤ 2500). Növbəti m sətirin hər biri yolları təsvir edir. Sətirlər a[i] b[i] d[i] formasındadır, bu da a[i] və b[i] çəmənliklərinin tam ədədi uzunluğu d[i] olan bir yol ilə birləşdirildiyini göstərir (1 ≤ a[i], b[i] ≤ n, 0 ≤ d[i] ≤ 2500). Hər çəmənlik ən azı bir yola bitişikdir və yollar arasında dövr yoxdur.
Çıxış Məlumatları
Bütün maraqlı yolların uzunluqlarının cəmini bir tam ədəd olaraq çıxarın. Yolların uzunluqlarının cəmi olduqca böyük ola biləcəyi üçün onların uzunluqlarının cəmini 10^9 + 7 modulu ilə çıxarın.
Nümunə
Bu nümunədə 6 mümkün yol var:
1 --> 2 --> 4 --> 5 --> 1 (uzunluğu 11)
1 --> 2 --> 5 --> 4 --> 1 (uzunluğu 11)
2 --> 3 --> 4 --> 5 --> 2 (uzunluğu 12)
2 --> 3 --> 5 --> 4 --> 2 (uzunluğu 12)
1 --> 2 --> 3 --> 4 --> 5 --> 1 (uzunluğu 15)
1 --> 2 --> 3 --> 5 --> 4 --> 1 (uzunluğu 15)
Cavab 12 + 12 + 15 + 15 = 54, burada yalnız uzunluğu ən azı 12 olan yollar toplanır.