$n$ 頂点の重み付きグラフが与えられます。番号が $1$ から $n-k$ までのすべての頂点（両端を含む）を含む、重みの総和が最小の連結部分グラフを求めてください。

問題を解きやすくし、テストデータも生成しやすくするため、入出力例以外のすべてのテストデータは次のアルゴリズムで生成されます。

• 出題者が整数 $n$、$m$、$k$ を選びます。
• 考えられるすべての $\frac{n\cdot(n-1)}{2}$ 本の辺をランダムな順序で検討します。
• 検討中の辺を追加した後でも、それ以降の辺を $0$ 本以上追加することで辺数が合計 $m$ 本以下の連結グラフにできる場合、その辺をグラフに追加します。
• 各辺の重みは、他の辺とは独立に、区間 $[50,100]$ 内の整数から一様ランダムに選びます。

入力

最初の行には $3$ つの整数 $n$（$5 \le n \le 100$）、$m$（$2\cdot n \le m \le 10\cdot n$）、$k$（$0 \le k \le 30$）が与えられます。続く $m$ 行にはそれぞれ $3$ つの整数 $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