У Егора есть взвешенный ориентированный граф, состоящий из n вершин. В этом графе между любой парой различных вершин есть ребро в обоих направлениях. Егор любит играть с графом, и сейчас он придумал новую игру:
- Игра состоит из n шагов.
- На i-том шаге Егор удаляет из графа вершину номер xi. Удаляя вершину, Егор удаляет все ребра, которые входили в данную вершину и которые выходили из нее.
- Перед выполнением каждого шага, Егор хочет знать сумму длин кратчайших путей между всеми парами оставшихся вершин. Кратчайший путь может проходить через любую оставшуюся вершину. Другими словами, если обозначить как d(i, v, u) кратчайший путь между вершинами v и u в графе, который получился до удаления вершины xi, то Егор хочет знать значение следующей суммы:
.
Помогите Егору, выведите значение искомой суммы перед каждым шагом.
Выходные данные
Выведите n целых чисел — i-тое число равно искомой сумме перед i-тым шагом.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на C++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
0
1
|
0
|
|
2
|
2
0 5
4 0
1 2
|
9 0
|
|
3
|
4
0 3 1 1
6 0 400 1
2 4 0 1
1 1 1 0
4 1 2 3
|
17 23 404 0
|