Cho đồ thị gồm ~ n ~ đỉnh và ~ m ~ cạnh. Các đỉnh được đánh số từ 1 đến ~ n ~, các cạnh có trọng số phân biệt là một số nguyên dương lũy thừa của 2. Hãy tính tổng độ dài đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị. (Cặp đỉnh ~ (u,v) ~ và ~ (v,u) ~ được xem là 1 cặp)

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương ~ n, m ~ cho biết số đỉnh và số cạnh trong đồ thị
• ~ m ~ dòng tiếp theo, mỗi dòng ghi 3 số nguyên ~ u, v, c ~ cho biết ~ 2^c ~ là trọng số của cạnh ~ (u,v) ~

Kết quả

• Một số nguyên duy nhất được biển diễn dưới dạng nhị phân là kết quả của bài toán.

Ràng buộc

• ~ 1 ≤ n ≤ 10^5 ~
• ~ 1 ≤ m ≤ 2.10^5 ~
• ~ 1 ≤ u, v ≤ n; u≠v ~
• ~ 0 ≤ c < m ~

Ví dụ:

Input 1

5 6
1 3 5
4 5 0
2 1 3
3 2 1
4 3 4
4 2 2 

Output 1

1000100