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