Farmer John לומד אלגוריתמים בקורס ערב באוניברסיטה המקומית, ובדיוק למד על עצים פורשים מינימליים. הוא מבין שעיצוב החווה יכול להיות יעיל יותר ורוצה לפשט את המבנה שלה.

החווה היא גרף: קודקודים הם שדות, קשתות הן שבילים ביניהם, לכל שביל אורך. Farmer John מבחין שלכל אורך יש לכל היותר שלושה שבילים. FJ רוצה להסיר שבילים ולקבל עץ, כלומר מסלול יחיד בין כל זוג שדות. הוא רוצה עץ פורש מינימלי עם סכום אורכי קשתות קטן ככל האפשר.

עזרו ל־Farmer John לחשב הן את סכום האורכים בעץ פורש מינימלי והן את מספר העצים הפורשים המינימליים השונים שיוכל ליצור.

קלט

• שורה $1$: שני שלמים $N$, $M$, $1 \le N \le 40,000; 1 \le M \le 100,000$, מספרי הקודקודים והקשתות בהתאמה. הקודקודים ממוספרים $1\ldots N$.
• שורות $2\ldots M+1$: שלושה שלמים $a_{i}$, $b_{i}$, $n_{i}$, $1 \le a_{i}, b_{i} \le N; 1 \le n_{i} \le 1,000,000$, מתארים קשת מ־$a_{i}$ ל־$b_{i}$ באורך $n_{i}$. שום אורך $n_{i}$ לא מופיע יותר משלוש פעמים.

פלט

• שורה $1$: שני שלמים, אורך העץ הפורש המינימלי ומספר העצים האלה מודולו $1,000,000,007$.

דוגמאות

קלט 1

4 5
1 2 1
3 4 1
1 3 2
1 4 2
2 3 2

פלט 1

4 3

הערה

בחירת שתי הקשתות באורך $1$ וכל קשת באורך $2$ נותנת עץ פורש מינימלי באורך $4$.

מחבר הבעיה: Nathan Pinsker, 2011