Welcome to the future!

There are N communication junctions on Mars, and K cities, each located at its own junction. Junctions are numbered from 1 to N, and a city is denoted as its junction number.

Company StarZ, the first one exploring Mars, wants to build a superfast transporting system, called SuperPipe, on Mars. They are already using that system on Earth and its by far the most efficient way to travel between distant places.

Now, city with number i is willing to pay $w_i$ for being connected to the SuperPipe system, not only because it’s extremely profitable for its people, but also highly prestigeous. Moreover, there are M pairs of junctions that can be connected by a line of SuperPipe, and it’s known that if all M lines are built, then it is possible to travel between any two junctions with a SuperPipe. However, connecting two junctions with a line of SuperPipe is not cheap. For each of M possible lines, StarZ knows the cost of building that line.

As a computer scientist in StarZ research lab, your task is to maximize the profit of building a SuperPipe network. The profit is defined as a sum of amount of money that cities connected to the network pay minus the sum of costs of building all the lines in the network. The only requirement is that the network has to be connected, i.e. it is possible to travel between any two junctions in the network.

Input format

In the first line, there are three space separated integer N, M and K, denoting the number of junctions, the number of possible pairs of junctions to be connected with a SuperPipe line, and the number of cities. In the second line, there are N space separated integers $w_1, w_2, \ldots, w_N$, where $w_i$ denotes the amount of money that will be earned by including the i-th junction in the network. Notice that exactly K of these integers are positive and they denote junctions with cities. Then M lines follow. In the i-th of them there are three space-separated integers $u_i$, $v_i$, $c_i$ and denotes that junctions $u_i$ and $v_i$ can be connected by a SuperPipe line with cost $c_i$.

Output format

In the first line, print two space separated integers X and Y, denoting respectively the number of junctions and the number of lines in the SuperPipe network. In the second line, print X space-separated integers denoting junctions in the network. After that, output Y lines, and in each of them print two space-separated integers denoting the pair of junctions in the network connected by a line.

Constraints

$N = 10^3$
$M \leq 100 \cdot N$
$0 \leq K \leq 500$
$0 \leq w_i \leq 10^4$
$1 \leq u_i, v_i \leq N$
$1 \leq c_i \leq 10^3$

Scoring

For a single test file its absolute score is the profit of the returned network. If the output for a particular test file is invalid then this score is 0. Formally, for V and E denoting respectively the set of junctions and the set of lines in the returned network, and $c(e)$ denoting the cost of building line e, the profit of such network is defined as:

$Profit(V, E) = \bigg(\sum\limits_{v \in V} w_v \bigg) - \bigg( \sum\limits_{e \in E} c(e) \bigg)$

The total absolute score of a submission is the sum of absolute scores across all test files. In this problem, scoring is set to relative, which means that the final score for a problem is your absolute score divided by the score of the best solution submitted by any participant. The objective is to maximize the total absolute score.

After the contest, new test files will be generated with the same method described below, and all submissions will be rejudged on these new test files.

Test generation

• M is generated uniformly at random from range $[5 \cdot N, 100 \cdot N]$
• K is generated uniformly at random from one of ranges: $[50,175]$, $[175,250]$, $[250,500]$, and all these ranges are used equal number of times among test files
• M pairs of junctions that can be connected by a line are generated using this graph generation method
• K non-zero values of $w_i$ are generated uniformly at random from a range $[1, 10^4]$, and these K junctions, denoting the cities, are also chosen uniformly at random from all N junctions
• Each cost of building a line between two junctions is generated uniformly at random from a range $[1, 10^3]$