В країн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