Складний тест
Андрій Сергійович зайнятий підготовкою задач до командної олімпіади. Розв'язання однієї з задач базується на алгоритмі Дейкстри і А.С. хоче підготувати складний тест для цього алгоритму.
Алгоритм Дейкстри діє наступним чином. Нехай G - це орієнтовний граф з множиною вершин V, множиною ребер E та ваговою функцією w : E → R^{+}. Нехай усі вершини досяжні з вершини s. Алгоритм використовує множину вершин U, спочатку ініційовану як порожню. Кожну вершину помічено або цілим числом, або +∞. Спочатку усі вершини помічені +∞, а вершину s помічено нулем. Позначимо мітку вершини v як d[v].
Крок алгоритму наступний: обирається вершина з мінімальною міткою, яка не входить в U. Нехай це вершина u. Вершина u додається до множини U і кожне ребро uv E релаксується. Релаксація замінює d[v] на min(d[v], d[u] + w(uv)). Алгоритм завершується, коли усі вершини додадно в U. Якщо мітка вершини v змінюється, релаксація називається активною.
Тепер Андрій Сергійович хоче створити граф з N вершинами та M ребрами, у якому алгоритм Дейкстри зробить максимально можливу кількість активних релаксацій. Допоможіть йому створити такий граф. Щоб уникнути невизначеності, нехай кожен раз існує рівно одна вершина, яка вибирається з мінімальною міткою з вершин, які не входять в U.
Вхідні дані
Перший рядок вхідного файлу містить два цілих числа: N та M - кількість вершин та ребер у графі, який Андрій хотів би створити (4 ≤ N ≤ 1000, N-1 ≤ M ≤ N^2/5).
Вихідні дані
У вихідний файл виведіть M рядків - ребра графа. Кожен рядок повинен містити три цілих числа: початок ребра, кінець ребра та його вагу. Усі ваги повинні бути невід'ємними і не повинні перевищувати 10^6. Усі вершини повинні бути досяжні з вершини з номером 1.
Якщо алгоритм Дейкстри починає роботу з вершини s=1 він повинен зробити максимально можливу кількість активних релаксацій серед усіх графів з N вершинами та M ребрами. Граф не повинен мати петель та кратних ребер.