Yollar

Olimpiya ölkəsində N şəhər və M yol mövcuddur. Yolların uzunluqları müxtəlifdir və 2^0-dan 2^(M-1)-ə qədər iki qüvvətidir. Bütün şəhər cütləri arasındakı ən qısa məsafələrin cəmini tapıb, nəticəni ikilik sistemdə təqdim edin.

Giriş məlumatları

Birinci sətirdə iki ədəd N və M verilir.

Sonrakı M sətirdə yollar təsvir edilir. Hər yol üç ədəd A, B, C ilə göstərilir, bu da A və B şəhərləri arasında uzunluğu 2^C olan ikitərəfli yolun olduğunu bildirir. Burada 1 ≤ A, B ≤ N, 0 ≤ C ≤ M - 1.

Bütün kənar uzunluqları unikaldır. Qrafın əlaqəli olduğu və düzgün verildiyi təmin edilir.

Çıxış məlumatları

Hər bir şəhər cütü arasındakı ən qısa məsafələrin cəmini ikilik sistemdə çıxarın. Nəzərə alın ki, cavab çox böyük ola bilər.

Məhdudiyyətlər

20 bal üçün 1 ≤ N, M ≤ 20

40 bal üçün 1 ≤ N, M ≤ 10^3

40 bal üçün 1 ≤ N, M ≤ 10^5

Nümunələr

Qiymətləndirmə

Testi daha yaxşı başa düşmək üçün qrafı çəkin.

1-dən 2-yə məsafə: 2^0

1-dən 3-ə məsafə: 2^0 + 2^2

1-dən 4-ə məsafə: 2^0 + 2^2 + 2^1

2-dən 3-ə məsafə: 2^2

2-dən 4-ə məsafə: 2^2 + 2^1

3-dən 4-ə məsafə: 2^1

Cəmi: 3 * 2^0 + 3 * 2^1 + 4 * 2^2 = 2^0 + 2^3 + 2^4 = 11001[2]