John lives in HackerLand, a country with $N$ cities and $\mbox{M}$ bidirectional roads. Each of the roads has a distinct length, and each length is a power of two (i.e., $2$ raised to some exponent). It's possible for John to reach any city from any other city.

Given a map of HackerLand, can you help John determine the sum of the minimum distances between each pair of cities? Print your answer in binary representation.

Input Format

The first line contains two space-seperated integers denoting $N$ (the number of cities) and $\mbox{M}$ (the number of roads), respectively.

Each line $\boldsymbol{i}$ of the $\mbox{M}$ subsequent lines contains the respective values of $A_i$, $B_i$, and $C_i$ as three space-separated integers. These values define a bidirectional road between cities $A_i$ and $B_i$ having length $2^{C_i}$.

Constraints

$1\leq N\leq10^5$
$1\leq M\leq2\times10^5$
$1\leq A_i,B_i\leq N$, $A_i\neq B_i$
$0\leq C_i<M$
If $i\neq j$, then $C_i\neq C_j$.

Output Format

Find the sum of minimum distances of each pair of cities and print the answer in binary representation.

Sample Input
5 6
1 3 5
4 5 0
2 1 3
3 2 1
4 3 4
4 2 2

Sample Output
1000100

Explanation

In the sample, the country looks like this:

Let $d(x,y)$ be the minimum distance between city $\boldsymbol{x}$ and city $y$.

$d(1,2)=8$

$d(1,3)=10$

$d(1,4)=12$

$d(1,5)=13$

$d(2,3)=2$

$d(2,4)=4$

$d(2,5)=5$

$d(3,4)=6$

$d(3,5)=7$

$d(4,5)=1$

$Sum=8+10+12+13+2+4+5+6+7+1=(68)_{10}=(1000100)_{2}$

见题面

见题面