Складний тест
Складний тест
Андрій Сергійович зайнятий підготовкою задач до командної олімпіади. Розв'язання однієї з задач базується на алгоритмі Дейкстри і А.С. хоче підготувати складний тест для цього алгоритму.
Алгоритм Дейкстри діє наступним чином. Нехай G - це орієнтовний граф з множиною вершин V, множиною ребер E та ваговою функцією w : E → R+. Нехай усі вершини досяжні з вершини 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 - кількість вершин та ребер у графі, який Андрій хотів би створити (4 ≤ N ≤ 1000, N-1 ≤ M ≤ N2/5).
Вихідні дані
У вихідний файл виведіть M рядків - ребра графа. Кожен рядок повинен містити три цілих числа: початок ребра, кінець ребра та його вагу. Усі ваги повинні бути невід'ємними і не повинні перевищувати 106. Усі вершини повинні бути досяжні з вершини з номером 1.
Якщо алгоритм Дейкстри починає роботу з вершини s=1 він повинен зробити максимально можливу кількість активних релаксацій серед усіх графів з N вершинами та M ребрами. Граф не повинен мати петель та кратних ребер.
Приклад
4 3
1 2 0 2 3 8 2 4 9
5 5
1 2 0 1 3 1 2 4 15 2 5 16 3 4 10