Вам задано зважений граф із $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