Given a weighted graph with $n$ vertices and $m$ edges, where each edge has a weight $w_i$, there are two types of queries:

1. Find the minimum variance spanning tree.
2. For each edge, find the minimum variance spanning tree of the remaining graph (containing $n$ vertices and $m-1$ edges) if that edge is removed.

You only need to output the minimum variance value. If the graph is not connected, output $-1$.

The variance of a spanning tree is defined as the variance of the weights of all its edges.

For $N$ variables $x_1, x_2, \dots, x_N$, the variance is calculated as $\sigma^2 = \frac{\sum_{1\leq i\leq N}(x_i-\mu)^2}{N}$, where $\sigma^2$ is the variance and $\mu$ is the mean. Since it is a spanning tree, $N = n-1$.

You need to output the variance multiplied by $N^2$. It can be proven that this value is an integer.

Input

The first line contains three integers $n, m, T$, representing the number of vertices, the number of edges, and the query type.

The next $m$ lines each contain three positive integers $u_i, v_i, w_i$, representing an edge connecting $u_i$ and $v_i$ with weight $w_i$. It is guaranteed that there are no self-loops, but multiple edges may exist.

Output

When $T=1$, output a single number representing the answer.

When $T=2$, output $m$ lines, each containing a number representing the answer if the $i$-th edge is removed.

If the graph is not connected, output $-1$.

Examples

Input 1

4 4 2
1 2 1
2 3 3
1 3 2
3 4 5

Output 1

14
26
24
-1

Subtasks

Property 1: The $i$-th edge connects vertex $(i \bmod n)+1$ and vertex $((i+1) \bmod n)+1$, and $w_i \le w_{i+1}$.