Дороги
Дороги
В країнi Олiмпiї є N мiст там M дорiг. Дороги мають рiзнi довжини, довжина є степенню двiйки вiд 20
до 2M-1
. Знайдiть суму всiх найкоротших вiдстаней та виведiть в двiйковому записi.
Вхідні дані
В першому рядку знаходиться два числа N та M.
В наступних M рядках задано дороги. Дорога задається 3 числами A,B,C, що означає, що мiж мiстами A та B є двонаправлена дорога довжини 2C
. 1 ≤ A,B ≤ N, 0 ≤ C ≤ M - 1
Всi довжини ребер рiзнi. Гарантується, що граф зв’язний i заданий корректно.
Вихідні дані
Виведiть суму найкоротших вiдстаней мiж кожною парою мiст в двiйковому записi. Звернiть увагу на те, що вiдповiдь може бути дуже великою.
Обмеження
20 балiв 1 ≤ N,M ≤ 20
40 балiв 1 ≤ N,M ≤ 103
40 балiв 1 ≤ N,M ≤ 105
Оцінювання
Для кращого розумiння тесту намалюйте граф.
Вiдстань вiд 1 до 2: 20
Вiдстань вiд 1 до 3: 20
+ 22
Вiдстань вiд 1 до 4: 20 +
2^2+
2^1`
Вiдстань вiд 2 до 3: 22
Вiдстань вiд 2 до 4: 22
+ 21
Вiдстань вiд 3 до 4: 21
Сумарно: 3 * 20
+ 3 * 21
+ 4 * 22
= 20
+ 23
+ 24
= 110012
4 4 1 2 0 2 3 2 1 3 3 3 4 1
11001