e-olymp
Задачи

Сложный тест

Сложный тест

Андрей Сергеевич занят подготовкой задач к командной олимпиаде. Решение одной из задач основано на алгоритме Дейкстры и А.С. хочет подготовить сложный тест для этого алгоритма.

Алгоритм Дейкстры действует следующим образом. Пусть G - это ориентированный граф с множеством вершин V, множеством ребер E и весововой функцией w : ER+. Пусть все вершины достижимы из вершины s. Алгоритм использует множество вершин U, изначально инициализированный как пустой. Каждая вершина помечена либо целым числом, либо +∞. Изначально все вершины помечены +∞, а вершина s помечена нулем. Обозначим метку вершины v как d[v].

Шаг алгоритма следующий: выбирается вершина с минимальной меткой, не входящая в U. Пусть это вершина u. Вершина u добавляется в множество U и каждое ребро uvTM_inEрелаксируется. Релаксация заменяет d[v] на min(d[v], d[u] + w(uv)). Алгоритм заканчивается, когда все вершины добавлены в U. Если метка вершины v изменяется, релаксация называется активной.

Теперь Андрей Сергеевич хочет создать граф с N вершинами и M ребрами, в котором алгоритм Дейкстры сделает максимально возможное количество активных релаксаций. Помогите ему создать такой граф. Чтобы избежать неопределенности, пусть каждый раз существует ровно одна вершина, которая выбирается с минимальной меткой из вершин, которые не входят в U.

Входные данные

Первая строка входного файла содержит два целых числа: N и M - число вершин и ребер в графе, который Андрей хотел бы создать (4N1000, N-1MN2/5).

Выходные данные

В выходной файл выведите M строк - рёбра графа. Каждая строка должна содержать три целых числа: начала ребра, конец ребра и его вес. Все веса должны быть неотрицательные и не должны превосходить 106. Все вершины должны быть доступны из вершины с номером 1.

Если алгоритм Дейкстры начинает работу из вершины s=1 он должен сделать максимальное возможное количество активных релаксаций среди всех графов с N вершинами и M ребрами. Граф не должен иметь петель и кратных рёбер.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
4 3
Выходные данные #1
1 2 0
2 3 8
2 4 9
Входные данные #2
5 5
Выходные данные #2
1 2 0
1 3 1
2 4 15
2 5 16
3 4 10