Gəlin qaçırılması
Dağların zirvələrində (əlbəttə ki, bizim bölgəmizdə deyil) hələ də qədim bir adət yaşadılır - gəlin qaçırmaq. Bir cigit bu adəti yerinə yetirməyə hazırlaşır. Onun yanında gözəl bir at var, ürək işlərində sadiq yoldaşı. Qaçırmanı uğurla həyata keçirmək üçün cigit real şəraitə yaxın şərtlərdə yaxşı məşq etməlidir.
Cigitlərin məşq etməsi üçün xüsusi bir yer mövcuddur. Burada N nöqtə var, 1-dən N-ə qədər nömrələnmiş və M yol mövcuddur. Qədim adətə görə, hər yolun cigitin hərəkət etməli olduğu tək bir istiqaməti var. Müvafiq yolda əks istiqamətdə hərəkət etmək təhlükəlidir (bütün digər cigitlər bunu qan düşməni kimi qəbul edirlər - bununla bağlı bütün nəticələrlə). Həmçinin hər yolun çətinliyi var, bu da natural ədəd ilə ifadə olunur. Bir cüt nöqtə arasında bir neçə yolun mövcudluğu və ya başlanğıc və son nöqtələri üst-üstə düşən dairəvi yolun mövcudluğu mümkündür.
Marşrut dedikdə, hər bir növbəti yolun (birincidən başqa) əvvəlki yolun bitdiyi nöqtədə başladığı boş olmayan yol ardıcıllığı nəzərdə tutulur. Faydalı marşrut isə hər bir yolun çətinliyinin (başlanğıcından başqa) əvvəlkindən daha yüksək olduğu marşrutdur.
Cigit 1 nöqtəsində başlayıb bitən bir marşrut seçməlidir. Əlbəttə ki, cigit yalnız faydalı marşrutlardan istifadə etməlidir.
Sizin vəzifəniz - cigitin sərəncamında neçə fərqli faydalı marşrut olduğunu tapmaqdır. Belə marşrutların sayı çox ola biləcəyi üçün, onların sayını 1000000000-ə bölünəndə qalanı hesablayın.
Giriş verilənləri
Birinci sətir N və M ədədlərini ehtiva edir. Növbəti M sətirin hər biri A_i, B_i, C_i tam ədədlərini ehtiva edir - i-ci yolun başlanğıc və son nöqtələri və onun çətinliyi müvafiq olaraq.
1 ≤ N ≤ 50000, 1 ≤ M ≤ 100000, 1 ≤ C_i ≤ 30000.
Çıxış verilənləri
Tək bir tam ədəd - faydalı marşrutların sayının 1000000000-ə bölünəndə qalanı.