Складний тест

Андрій Сергійович зайнятий підготовкою задач до командної олімпіади. Розв'язання однієї з задач базується на алгоритмі Дейкстри і А.С. хоче підготувати складний тест для цього алгоритму.

Алгоритм Дейкстри діє наступним чином. Нехай 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.

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