Андрей Сергеевич занят подготовкой задач к командной олимпиаде. Решение одной из задач основано на алгоритме Дейкстры и А.С. хочет подготовить сложный тест для этого алгоритма. Алгоритм Дейкстры действует следующим образом. Пусть \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} ребрами. Граф не должен иметь петель и кратных рёбер.