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 (max 3 egyformát ajánl), 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 ≤ N ≤ 50000, 1 ≤ M ≤ 200000), majd a következő M sorból az ai, bi, ci szóközzel elválasztott egészeket, melyek jelentése: az ai városból a bi városba építhetünk ci (1 ≤ ci ≤ 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 109 + 7-tel vett osztási maradékát.
4 5
1 2 1
3 4 1
1 3 2
1 4 2
2 3 2
4 3
Ha az 1 hosszúságú éleket, és bármelyik 2 hosszúságú élet választjuk, akkor kapjuk a legrövidebbet.