يدرس 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