Edges and Divisors

Time limit: 1000 ms. Memory limit: 2048 MB.

We play a game on a directed acyclic graph $G = (V, E)$. We start at vertex $s\_1 \in V$. The rules are as follows:

• The game consists of rounds numbered from $1$.
• In the $i$-th round, the player selects a path $p\_i$ that starts at $s\_i$ and contains at least one edge, such that the sum of the weights of its edges is an exact multiple of $(i + 1)$. If no such path exists, the player fails and scores no points. Otherwise, the round ends successfully, and the endpoint of $p\_i$ is recorded as $s\_{i + 1}$.
• After a successful round, the player can either end the game or continue with the next round. If the player ends the game, the selected $i$ paths $p\_1, \ldots, p\_i$ are called doubling paths, and the score is calculated.

If the player has not failed, then when the game ends, the score for the selected doubling paths $p\_1, \ldots, p\_k$ is $\sum\_{i = 1}^{k} a\_i \left|p\_i\right| / k$, where $|p\_i|$ is the number of edges in path $p\_i$, and $a\_i$ is the weight given in the input. Since the graph is acyclic, at most $(n-1)$ paths can be selected, so the input provides only the weights $a\_1, \ldots, a\_{n-1}$.

Given the graph and the starting vertex, compute the maximum achievable score.

The first line contains three integers $n$, $m$, and $s\_1$: the number of vertices, the number of edges, and the index of the starting vertex ($2 \le n \le 100$; $1 \le m \le \frac{n (n - 1)}{2}$; $1 \le s\_1 \le n$).

The second line contains $(n-1)$ integers $a\_1, \ldots, a\_{n-1}$, the weights used to calculate the score ($1 \le a\_1 \le a\_2 \le \ldots \le a\_{n - 1} \le 10^9$).

Each of the next $m$ lines contains three integers $u\_i$, $v\_i$, and $w\_i$, describing a directed edge from $u\_i$ to $v\_i$ with weight $w\_i$ ($1 \le u\_i, v\_i \le n$; $u\_i \ne v\_i$; $1 \le w\_i \le 10^9$). The graph is acyclic, connected when edges are treated as undirected, and has no multiple edges.

Output a single line containing two integers separated by a space.

If at least one path can be selected, an optimal selection scheme exists, and the optimal score can be written as $p/q$ where $p$ and $q$ are coprime integers and $q > 0$. In this case, output $p$ and $q$. Otherwise, if no path can be selected, output -1~-1.

The selected doubling paths are $p\_1 = ((1, 2))$ and $p\_2 = ((2, 5))$.