Дороги
В країнi Олiмпiї є N мiст там M дорiг. Дороги мають рiзнi довжини, довжина є степенню двiйки вiд 2^0 до 2^(M-1) . Знайдiть суму всiх найкоротших вiдстаней та виведiть в двiйковому записi.
Вхідні дані
В першому рядку знаходиться два числа N та M.
В наступних M рядках задано дороги. Дорога задається 3 числами A,B,C, що означає, що мiж мiстами A та B є двонаправлена дорога довжини 2^C. 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 ≤ 10^3
40 балiв 1 ≤ N,M ≤ 10^5
####Оцінювання
Для кращого розумiння тесту намалюйте граф.
Вiдстань вiд 1 до 2: 2^0
Вiдстань вiд 1 до 3: 2^0 + 2^2
Вiдстань вiд 1 до 4: 2^0 + 2^2+2^1`
Вiдстань вiд 2 до 3: 2^2
Вiдстань вiд 2 до 4: 2^2 + 2^1
Вiдстань вiд 3 до 4: 2^1
Сумарно: 3 * 2^0 + 3 * 2^1 + 4 * 2^2 = 2^0 + 2^3 + 2^4 = 11001[2]