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