Dağ cığırları#1773
Bir dağ gəzintiçisi dağlarda məşq marşrutu planlaşdırır. Məşq üçün -dən -ə qədər nömrələnmiş dayanıcılıq nquətəsi və cığır var. Hər cığır yalnız bir istiq amətdə (çıxan və ya enən) keçilə bilər. Hər cığırın çətinlik dərəcəsi təbii ədədlə verilir. İki nqtə arasında bir neçə cığır ola bilər və ya döngəvi cığır da (başlanğıc və son nöqtəsi eynidir).
Marşrut — boş olmayan cığır ardıcıllığıdır, belə ki, hər sonrakı cığır (əvvəlkindən başqa) əvvəlki cığırın bitdiyi yerdə başlayır. Faydalı məşq marşrutu isə odur ki, hər cığırın çətinliyi əvvəlkindən (birincidən başqa) ciddi şəkildə böyükdür.
Gəzinçi yalnız baza (nöqtə )-dən başlayıb baza-da bitən marşrut seçməlidir. O, yalnız faydalı məşq marşrutlarına baxa bilər.
Sənin tapşırığın — neçə müxtəlif faydalı marşrutun mövcud olduğunu saymaqdır. Çox ola biləcəyi üçün onların sayını -a bölünmədən qalan ilə çıxış et.
Birinci sətrin daxilində və tam ədədləri verilir. Növbəti sətrin hər biri üç tam ədəd A_i, B_i, C_i — -ci cığırın başlanğıc və son nöqtələrinin nömrələri və onun çətinlik dərəcəsi verilir.
1 \leq N \leq 50000, 1 \leq M \leq 100000, 1 \leq C_i \leq 30000.
Bir tam ədəd — faydalı marşrutların sayını -a bölmə üzrə qalığı çap et.
Nümunə 1