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 \leq N \leq 50000, 1 \leq M \leq 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 \leq c_i \leq 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 \(10^9+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.