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