Задача N. В помощь курьерам! ≡

Условие

Одна курьерская компания, занимающаяся междугородными перевозками крупногабаритных грузов, решила упростить жизнь своим сотрудникам. Для этого перед программистами поставили задачу, определить наиболее короткие маршруты, по которым можно было бы доставлять грузы между различными населенными пунктами.

В качестве входных данных им выдали дорожную карту, представленную в виде взвешенного графа, вершины которого отвечают за населенные пункты, а ребра обозначают соединяющие их двусторонние магистрали. Каждое ребро имеет вес, указывающий длину соответствующей магистрали.

На выходе требуется получить список кратчайших маршрутов между всеми возможными парами вершин в таком графе. При этом среди них приоритетными считаются маршруты с максимально возможным числом остановок в промежуточных пунктах, т.е. проходящие через как можно большее число вершин.

Формат входного файла

В начале входного файла "input.txt" записаны два натуральных числа: n — число вершин и m — число соединяющих их ребер. Далее следует набор из m таких ребер, каждое из которых представлено тройкой целых чисел: (a_i, b_i) — номера вершин, w_i — вес ребра. При этом полагается, что нумерация вершин начинается с нуля.

Формат выходного файла

В выходной файл "output.txt" следует построчно вывести маршруты, удовлетворяющие условию задачи и представленные в виде последовательностей из номеров вершин. Если для какой-либо пары вершин существует более одного такого маршрута, достаточно будет вывести любой из них.

Ограничения

Гарантируется, что исходный граф является связным, т.е. между любой парой его вершин можно проложить маршрут.

2 ≤ n ≤ 200, 1 ≤ m ≤ (n ⋅ (n − 1)) / 2,

0 ≤ (a_i, b_i) < n, 0 < w_i ≤ 10

Примеры тестов

4
5
0 1 6
1 2 3
1 3 5
2 3 2
3 0 1

0 3 2 1
0 3 2
0 3
1 2
1 2 3
2 3

4
5
0 2 1
1 2 2
1 3 3
2 3 4
3 0 6

0 2 1
0 2
0 2 3
1 2
1 3
2 3