畀你一張有 $n$ 個頂點嘅加權圖。你要搵一個總權重最細嘅連通子圖，包含編號由 $1$ 到 $n-k$ 嘅所有頂點（包括兩端）。

為咗令問題容易啲解、測試數據容易啲產生，除咗例子之外，所有測試數據都係用以下算法產生：

• 出題人揀選整數 $n$、$m$ 同 $k$。
• 以隨機次序考慮全部 $\frac{n\cdot(n-1)}{2}$ 條可能嘅邊。
• 考慮一條邊嗰陣，如果加咗佢之後，仲可以加入之後嘅零條或者多條邊，得到一張總邊數唔超過 $m$ 嘅連通圖，就將佢加落圖。
• 每條邊嘅權重都係由區間 $[50,100]$ 入面獨立、均勻隨機咁揀一個整數。

輸入格式

第一行有三個整數 $n$（$5 \le n \le 100$）、$m$（$2\cdot n \le m \le 10\cdot n$）同 $k$（$0 \le k \le 30$）。跟住 $m$ 行，每行有三個整數 $a_i$、$b_i$ 同 $w_i$（$1 \le a_i < b_i \le n$，$50 \le w_i \le 100$），表示頂點 $a_i$ 同 $b_i$ 之間有一條權重係 $w_i$ 嘅邊。

保證張圖冇自環同重邊。另外，保證除咗例子之外，所有測試數據嘅圖都係用上面嘅算法產生。

輸出格式

第一行輸出一個整數 $c$，代表揀咗嘅子圖有幾多條邊。跟住 $c$ 行輸出揀咗嘅邊：每行寫一條邊連住嘅兩個頂點編號。如果有幾個答案，輸出任何一個都得。

例子

輸入格式 1

5 10 3
1 2 50
1 3 51
1 4 52
1 5 53
2 3 54
2 4 55
2 5 56
3 4 57
3 5 58
4 5 59

輸出格式 1

1
1 2

輸入格式 2

5 10 2
1 2 100
1 3 100
1 4 57
1 5 56
2 3 100
2 4 54
2 5 53
3 4 52
3 5 51
4 5 50

輸出格式 2

3
5 2
5 3
1 5