eolymp
Задачі

Складний тест

Складний тест

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Андрій Сергійович зайнятий підготовкою задач до командної олімпіади. Розв'язання однієї з задач базується на алгоритмі Дейкстри і А.С. хоче підготувати складний тест для цього алгоритму.

Алгоритм Дейкстри діє наступним чином. Нехай G - це орієнтовний граф з множиною вершин V, множиною ребер E та ваговою функцією w : ER+. Нехай усі вершини досяжні з вершини s. Алгоритм використовує множину вершин U, спочатку ініційовану як порожню. Кожну вершину помічено або цілим числом, або +∞. Спочатку усі вершини помічені +∞, а вершину s помічено нулем. Позначимо мітку вершини v як d[v].

Крок алгоритму наступний: обирається вершина з мінімальною міткою, яка не входить в U. Нехай це вершина u. Вершина u додається до множини U і кожне ребро uvEрелаксується. Релаксація замінює d[v] на min(d[v], d[u] + w(uv)). Алгоритм завершується, коли усі вершини додадно в U. Якщо мітка вершини v змінюється, релаксація називається активною.

Тепер Андрій Сергійович хоче створити граф з N вершинами та M ребрами, у якому алгоритм Дейкстри зробить максимально можливу кількість активних релаксацій. Допоможіть йому створити такий граф. Щоб уникнути невизначеності, нехай кожен раз існує рівно одна вершина, яка вибирається з мінімальною міткою з вершин, які не входять в U.

Вхідні дані

Перший рядок вхідного файлу містить два цілих числа: N та M - кількість вершин та ребер у графі, який Андрій хотів би створити (4N1000, N-1MN2/5).

Вихідні дані

У вихідний файл виведіть M рядків - ребра графа. Кожен рядок повинен містити три цілих числа: початок ребра, кінець ребра та його вагу. Усі ваги повинні бути невід'ємними і не повинні перевищувати 106. Усі вершини повинні бути досяжні з вершини з номером 1.

Якщо алгоритм Дейкстри починає роботу з вершини s=1 він повинен зробити максимально можливу кількість активних релаксацій серед усіх графів з N вершинами та M ребрами. Граф не повинен мати петель та кратних ребер.

Приклад

Вхідні дані #1
4 3
Вихідні дані #1
1 2 0
2 3 8
2 4 9
Вхідні дані #2
5 5
Вихідні дані #2
1 2 0
1 3 1
2 4 15
2 5 16
3 4 10