| Codeforces Round 241 (Div. 2) |
|---|
| Закончено |
В старой доброй Берляндии n городов, m дорог. Каждая из дорог соединяет пару различных городов и является двусторонней. Между парой городов не более одной дороги. Известна длина каждой из дорог.
Известно, что совсем скоро Президент поедет по дорогам Берляндии из города s в город t. Конечно, он выберет один из кратчайших путей из s в t, но какой именно — не известно.
Министр транспорта очень боится, что Президент будет расстроен состоянием дорог страны. По этой причине он планирует организовать ремонт тех дорог, по которым может проходить путь Президента.
Составить бюджет для такого мероприятия — непростая задача. Для всех возможных различных пар s, t (s < t) найдите количество дорог, которые лежат на хотя бы одном кратчайшем пути из s в t.
В первой строке входных данных записаны целые числа n, m (2 ≤ n ≤ 500, 0 ≤ m ≤ n·(n - 1) / 2) — количество городов и дорог соответственно. Далее следует m строк с описаниями дорог, по одному описанию в строке. Каждое описание содержит три целых числа xi, yi, li (1 ≤ xi, yi ≤ n, xi ≠ yi, 1 ≤ li ≤ 106), где xi, yi — номера соединяемых i-й дорогой городов, а li — ее длина.
Выведите последовательность 
целых чисел c12, c13, ..., c1n, c23, c24, ..., c2n, ..., cn - 1, n, где cst — искомое количество дорог на пути из s в t. Элементы последовательности c выводите в описанном порядке. Если между парой городов s и t вообще нет пути, то cst = 0.
5 6
1 2 1
2 3 1
3 4 1
4 1 1
2 4 2
4 5 4
1 4 1 2 1 5 6 1 2 1
