給定一張有 $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