Statement - 2015. december (s103)

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.

Input

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.

Output

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.

Example

Input

Copy

Output

Copy

4 3

Notes

Ha az 1 hosszúságú éleket, és bármelyik 2 hosszúságú élet választjuk, akkor kapjuk a legrövidebbet.

Information

Identifier:

s103

Title:

2015. december

Time limit:

3000 ms

Memory limit:

64 MiB

Tags:

show

Task type:

batch

Fordítási parancsok

C++ 11:

/usr/bin/g++ -O2 -static -DONLINE_JUDGE -std=c++11 main.cpp
a.out

C++ 14:

/usr/bin/g++ -O2 -static -DONLINE_JUDGE -std=c++14 main.cpp
a.out

C++ 17:

/usr/bin/g++ -O2 -static -DONLINE_JUDGE -std=c++17 main.cpp
a.out

C# (mono):

/usr/bin/mcs -out:main.exe -optimize+ main.cs
/usr/bin/mono main.exe

Go:

/usr/bin/gccgo main.go
a.out

Java:

/usr/bin/javac -cp . main.java
/usr/bin/java -cp . main

Julia:

/usr/local/bin/julia main.jl

Pascal:

/usr/bin/fpc -Mobjfpc -O2 -Xss main.pas
main

PyPy 3:

/usr/bin/pypy3 main.py

Python 3:

/usr/bin/python3 main.py

Submit solution

Beküldéshez lépj be vagy regisztrálj!

Attachments

Statement (english)