Вам дан взвешенный граф на $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