Roads

In the country of Olympia, there are N cities connected by M roads. Each road has a unique length, which is a power of two ranging from 2^0 to 2^(M-1). Your task is to calculate the sum of all shortest distances between every pair of cities and present the result in binary form.

Input

The first line contains two integers, N and M.

The following M lines each describe a road with three integers A, B, C. This indicates a bidirectional road of length 2^C exists between cities A and B. Here, 1 ≤ A, B ≤ N and 0 ≤ C ≤ M - 1.

Each road has a unique length, and it is guaranteed that the graph is connected and properly defined.

Output

Print the sum of the shortest distances between all pairs of cities in binary form. Note that the result can be very large.

Constraints

• 20 points: 1 ≤ N, M ≤ 20

• 40 points: 1 ≤ N, M ≤ 10^3

• 40 points: 1 ≤ N, M ≤ 10^5

Evaluation

To better understand the problem, consider drawing the graph.

Example distances:

• From city 1 to city 2: 2^0

• From city 1 to city 3: 2^0 + 2^2

• From city 1 to city 4: 2^0 + 2^2 + 2^1

• From city 2 to city 3: 2^2

• From city 2 to city 4: 2^2 + 2^1

• From city 3 to city 4: 2^1

Total sum: 3 * 2^0 + 3 * 2^1 + 4 * 2^2 = 2^0 + 2^3 + 2^4 = 11001[2]

Examples