Description

There are two ways to obtain a potion: you can either configure it yourself according to the magic book, or buy it at the magic shop — every kind of potion is available there, though the price may be high. The magic book contains many notes like this:

Mixing $1$ unit of potion A with $1$ unit of potion B yields $1$ unit of potion C. (As for why $1 + 1 = 1$, well... this is the magic world.) Now, you know which potion you need, you also know the prices of all potions that may be involved and all recipes in the magic book. The questions are:

1. What is the minimum cost to successfully produce this precious potion?
2. How many different minimum-cost plans are there (two feasible configuration plans are considered different if any step differs)? Assume you initially have no usable potion.

Input Format

The first line contains an integer $N$ ($1 \le N \le 1000$), the total number of potions involved. Potions are numbered from $0$ to $N - 1$, and potion No. $0$ is the final target potion.

The second line contains $N$ integers, giving the prices (for $1$ unit each) of all potions numbered from $0$ to $N - 1$ in order at the magic shop.

From the third line onward, each line contains three integers A, B, C, meaning mixing $1$ unit of potion A with $1$ unit of potion B yields $1$ unit of potion C. Note that if a specific pair of potions can be mixed to form a new potion, the result is unique. In other words, there will not be two lines where A and B are the same but C is different.

The input ends with a blank line.

Output Format

Output two integers separated by a space, representing the minimum cost to obtain potion No. $0$ and the number of minimum-cost plans.

It is guaranteed that the number of plans does not exceed $2^{63} - 1$.

7 
10 5 6 3 2 2 3 
1 2 0 
4 5 1 
3 6 2

10 3

Hint

Constraints:

The price of each potion is within $[1, 2.8\times 10^4]$.

Sample explanation:

There are $3$ optimal plans:

• Buy potion No. $0$ directly.
• Buy potion No. $4$ and potion No. $5$ to make potion No. $1$, buy potion No. $2$ directly, then combine to make potion No. $0$.
• Buy potion No. $4$ and potion No. $5$ to make potion No. $1$, buy potion No. $3$ and potion No. $6$ to make potion No. $2$, then combine to make potion No. $0$.

Translated by ChatGPT 5