There is a country consisting of $n$ cities connected by $m$ bidirectional roads. The $i$-th road connects city $u_i$ and city $v_i$; however, due to construction delays, the $i$-th road is only open from day $w_i$ onwards. It is guaranteed that all roads are distinct, each road connects two different cities, and after all roads are open, all cities are reachable from city $1$.

Each city has several street lamps for night lighting. After each night falls, every lamplighter lights the lamps only in the city they are currently in; after sunrise, the lamplighter extinguishes the lamps in that city. Initially, there are sufficiently many lamplighters in city $1$. This is recorded as night $0$.

To illuminate every city in the country, each lamplighter must move along the roads between cities during the day. Specifically, for each positive integer $t$, if a lamplighter is in city $x$ on night $t-1$, they must move along a road that has one endpoint at city $x$ and is already open (i.e., its $w$ value is at most $t$), and arrive at the other endpoint of the road exactly on night $t$. If there are multiple different roads, each lamplighter will independently choose one at random; in particular, if no such road exists, the lamplighter will leave the country in disappointment.

You want to know if there exists a non-negative integer $d$ such that on night $d$, the lamps in all cities are lit; in other words, on night $d$, there is at least one lamplighter in every city. If it exists, you also want to find the minimum possible $d$ that satisfies the condition.

For certain reasons, given a parameter $o \in \{0, 1\}$, you only need to output the value of $o \cdot d$ if $d$ exists.

Input

This problem contains multiple test cases.

The first line contains two integers $c$ and $T$, representing the test case ID and the number of test cases, respectively. The following lines contain each test case. The sample satisfies $c = 0$.

For each test case:

• The first line contains three positive integers $n$, $m$, and $o$, representing the number of cities, the number of roads, and the given parameter, respectively.
• The next $m$ lines each contain three integers $u_i, v_i, w_i$.

It is guaranteed that all roads are distinct, each road connects two different cities, and after all roads are open, all cities are reachable from city $1$.

Output

For each test case, output a single integer on a line:

• If a non-negative integer $d$ satisfying the condition exists, output the product of the minimum possible $d$ and $o$.
• If no such non-negative integer $d$ exists, output $-1$.

Examples

Input 1

0 2
4 4 1
2 1 2
1 3 1
1 4 1
3 4 2
3 2 1
1 2 2
1 3 3

Output 1

3
-1

Note 1

For the first test case:

• On night $0$, only city $1$ has sufficiently many lamplighters, so the lit city is city $1$.
• On day $1$, all lamplighters in city $1$ move to cities $3$ and $4$. Note that lamplighters cannot move to city $2$ because the road $(1, 2)$ is only completed after day $w = 2$. Therefore, on night $1$, the lit cities are $3$ and $4$; since there are sufficiently many lamplighters, some will reach city $3$ and others will reach city $4$.
• On day $2$, all lamplighters in city $3$ move to cities $1$ and $4$, and all lamplighters in city $4$ move to cities $1$ and $3$. Therefore, on night $2$, the lit cities are $1, 3,$ and $4$.
• On day $3$, all lamplighters in city $1$ move to cities $2, 3,$ and $4$, those in city $3$ move to cities $1$ and $4$, and those in city $4$ move to cities $1$ and $3$. Therefore, on night $3$, all cities are lit.

Thus, $d = 3$, and the output is $o \cdot d = 3$.

For the second test case, on day $1$, all roads connected to city $1$ are not yet open, so all lamplighters are unable to move and will leave the country. Therefore, no such $d$ exists, and the output is $-1$.

Input 2

(See attachment lamplighter/lamplighter2.in)

Output 2

(See attachment lamplighter/lamplighter2.ans)

Input 3

(See attachment lamplighter/lamplighter3.in)

Output 3

(See attachment lamplighter/lamplighter3.ans)

Input 4

(See attachment lamplighter/lamplighter4.in)

Output 4

(See attachment lamplighter/lamplighter4.ans)

Input 5

(See attachment lamplighter/lamplighter5.in)

Output 5

(See attachment lamplighter/lamplighter5.ans)

Input 6

(See attachment lamplighter/lamplighter6.in)

Output 6

(See attachment lamplighter/lamplighter6.ans)

Input 7

(See attachment lamplighter/lamplighter7.in)

Output 7

(See attachment lamplighter/lamplighter7.ans)

Input 8

(See attachment lamplighter/lamplighter8.in)

Output 8

(See attachment lamplighter/lamplighter8.ans)

Constraints

There are 25 test cases in total, each worth 4 points.

For all data, it is guaranteed that:

• $1 \leq T \leq 10$
• $2 \leq n \leq 2.5\times 10^4$
• $n - 1 \leq m \leq 5\times 10^4$
• $o \in \{0, 1\}$
• For all $1 \leq i \leq m$, $1 \leq u_i, v_i \leq n$, $u_i \neq v_i$, $1 \leq w_i \leq 10^9$
• All bidirectional roads are distinct
• After all roads are open, all cities are reachable from city $1$

• Special Property A: $w_i \leq 2\times 10^5$ is guaranteed.
• Special Property B: All $w_i$ are equal.
• Special Property C: A non-negative integer $d$ is guaranteed to exist.