Egy országban $N$ város található. Megbíztak minket, hogy tervezzünk utakat a városok közt úgy, hogy bármelyik városból bármelyikbe egyféleképp lehessen eljutni. Mivel egy út megépítésének költsége egyenesen arányos a hosszával, így szeretnénk minimalizálni a megépülő utak összes hosszát. Az országban nagy hegyek is vannak, ezért nem építhetünk utat bármely két város között, hanem csak a bemenő adatokban megadott $M$ db utat lehet megépíteni. Az útépítést vállaló cég technikai okok miatt nem tud egy adott úthosszból háromnál többet megépíteni, ezért az úthálózatot úgy kell kialakítani, hogy bármely hosszúságú útból legföljebb három szerepeljen benne. Kérdés, hogy hányféleképp tudjuk megépíteni a lehető legkisebb összhosszúságú úthálózatot.
A program olvassa be a standard input első sorából $N$-et és $M$-et ($1\le N\le 50000$, $1\le M\le 200000$), majd a következő $M$ sorból az $a_i$, $b_i$, $c_i$ szóközzel elválasztott egészeket, melyek jelentése: az $a_i$ városból a $b_i$ városba építhetünk $c_i$ ($1\le c_i\le 1000000$) hosszú kétirányú utat. A program írja a standard output első és egyetlen sorába a legrövidebb összhosszúságot, amelyből megépíthető a hálózat, illetve a lehetőségek számának $1000000007$-tel vett osztási maradékát.