Warehouses

UCPC City has $N$ warehouses, and $K$ companies each own some of them. The warehouses are numbered from $1$ to $N$, and the companies are numbered from $1$ to $K$. $M$ bidirectional roads connect pairs of warehouses, and each road has a transfer limit. Two warehouses may be connected by several roads, and there is always a path between any two warehouses.

Suppose goods are shipped between two warehouses. The shipping limit between them is the smallest transfer limit among the roads on a path connecting them. If several paths connect the two warehouses, the path with the largest shipping limit is chosen.

For each company, compute the sum of the shipping limits over all pairs of warehouses owned by that company.

Each company is guaranteed to own at least 2 warehouses.

The first line contains three integers $N$, $K$, and $M$, separated by spaces. $(2\leq N\leq 100\ 000;\ 1\leq K\leq\min(\frac{N}{2} ,50\ 000) ;\ N-1\leq M\leq 300\ 000)$

The second line contains $N$ integers $C_1, C_2, ..., C_N$, separated by spaces. Warehouse $i$ is owned by company $C_i$. $(1\leq C_i\leq K)$

The next $M$ lines each contain three integers $X$, $Y$, and $W$, separated by spaces. Each line describes a bidirectional road between warehouses $X$ and $Y$ with transfer limit $W$. $(1\leq X,Y\leq N;\ 1\leq W\leq 10^9)$

Print $K$ lines. The $i$-th line contains the sum of shipping limits over all pairs of warehouses owned by company $i$, for $i$ from $1$ to $K$.