간선과 약수

시간 제한: 1000 ms. 메모리 제한: 2048 MB.

방향 비순환 그래프 $G = (V, E)$에서 게임을 합니다. 시작 정점은 $s\_1 \in V$입니다. 규칙은 다음과 같습니다.

• 게임은 1번부터 번호가 매겨진 라운드로 진행됩니다.
• $i$번째 라운드에서 플레이어는 $s\_i$에서 시작하고 간선을 하나 이상 포함하는 경로 $p\_i$를 고릅니다. 이때 경로에 속한 간선 가중치의 합이 $(i + 1)$의 정확한 배수여야 합니다. 그런 경로가 없으면 플레이어는 실패하고 점수를 얻지 못합니다. 고를 수 있으면 라운드가 성공하여 끝나고, $p\_i$의 끝점을 $s\_{i + 1}$로 기록합니다.
• 라운드에 성공한 뒤 플레이어는 게임을 끝내거나 다음 라운드를 계속할 수 있습니다. 게임을 끝내면 고른 $i$개의 경로 $p\_1, \ldots, p\_i$를 이중 경로(doubling paths)라 하고, 점수를 계산합니다.

실패하지 않았다면, 게임을 끝낼 때 고른 이중 경로 $p\_1, \ldots, p\_k$의 점수는 $\sum\_{i = 1}^{k} a\_i \left|p\_i\right| / k$입니다. 여기서 $|p\_i|$는 경로 $p\_i$의 간선 수이고, $a\_i$는 입력으로 주어진 가중치입니다. 그래프가 비순환이므로 고를 수 있는 경로는 최대 $(n-1)$개이며, 입력에는 $a\_1, \ldots, a\_{n-1}$만 주어집니다.

그래프와 시작 정점이 주어졌을 때, 얻을 수 있는 최대 점수를 구하세요.

첫 줄에 정수 $n$, $m$, $s\_1$이 주어집니다. 각각 정점 수, 간선 수, 시작 정점 번호입니다 ($2 \le n \le 100$; $1 \le m \le \frac{n (n - 1)}{2}$; $1 \le s\_1 \le n$).

둘째 줄에는 점수 계산에 쓰이는 $(n-1)$개의 정수 $a\_1, \ldots, a\_{n-1}$이 주어집니다 ($1 \le a\_1 \le a\_2 \le \ldots \le a\_{n - 1} \le 10^9$).

이어지는 $m$개의 줄에는 각각 정수 $u\_i$, $v\_i$, $w\_i$가 주어지며, 이는 $u\_i$에서 $v\_i$로 가는 가중치 $w\_i$의 유향 간선입니다 ($1 \le u\_i, v\_i \le n$; $u\_i \ne v\_i$; $1 \le w\_i \le 10^9$). 그래프는 비순환이고, 방향을 무시하면 연결되어 있으며, 중복 간선은 없습니다.

한 줄에 공백으로 구분된 정수 두 개를 출력합니다.

경로를 하나 이상 고를 수 있으면 최적의 선택 방법이 존재하고, 최적 점수는 서로소인 정수 $p$, $q$ ($q > 0$)에 대해 $p/q$로 나타낼 수 있습니다. 이 경우 $p$와 $q$를 출력합니다. 경로를 하나도 고를 수 없으면 -1~-1을 출력합니다.

선택된 이중 경로는 $p\_1 = ((1, 2))$와 $p\_2 = ((2, 5))$입니다.