일자리 찾기

베시는 돈이 다 떨어져서 일자리를 찾고 있습니다. 농부 존은 이를 알고 소들이 여기저기 돌아다니기를 바라며, 소는 한 도시에서 최대 $D$ ($1 \le D \le 1000$) 달러를 벌면 반드시 다른 도시로 가서 일해야 한다는 규칙을 세웠습니다. 다만 베시는 다른 곳에서 얼마간 일한 뒤 어떤 도시로 다시 돌아와 그 도시에서 또다시 최대 $D$ 달러를 벌 수 있습니다. 이렇게 할 수 있는 횟수에는 제한이 없습니다.

베시의 세계는 $C$ ($2 \le C \le 220$)개의 도시를 잇는 $P$ ($1 \le P \le 150$)개의 일방통행 도로로 이루어져 있으며, 도시는 $1$번부터 $C$번까지 번호가 매겨져 있습니다. 베시는 현재 도시 $S$ ($1 \le S \le C$)에 있습니다. $i$번째 도로는 도시 $A_i$에서 도시 $B_i$로 가는 일방통행이며 ($1 \le A_i \le C$; $1 \le B_i \le C$), 통행 비용은 없습니다.

베시를 돕기 위해 농부 존은 자신의 전용 제트기 서비스를 이용하게 해 줍니다. 이 서비스는 $F$ ($1 \le F \le 350$)개의 노선을 제공하며, 각 노선은 도시 $J_i$에서 다른 도시 $K_i$로 가는 일방통행 항공편으로 ($1 \le J_i \le C$; $1 \le K_i \le C$), 요금은 $T_i$ ($1 \le T_i \le 50000$) 달러입니다. 베시는 수중에 현금이 없어도 앞으로 벌 돈으로 항공권 값을 낼 수 있습니다.

베시는 언제 어디서든 은퇴할 수 있습니다. 시간이 무한히 주어질 때, 베시가 갈 수 있는 모든 도시에서 최대 $D$ 달러를 번다고 가정하면 그녀가 벌 수 있는 최대 금액은 얼마입니까? 이 금액에 한계가 없다면 $-1$을 출력하세요.

• 첫째 줄: 공백으로 구분된 다섯 개의 정수 $D$, $P$, $C$, $F$, $S$
• 다음 $P$개의 줄: $i$번째 줄에는 한 도시에서 다른 도시로 가는 일방통행 도로를 나타내는 두 정수 $A_i$와 $B_i$가 공백으로 구분되어 주어집니다.
• 그다음 $F$개의 줄: 각 줄에는 한 도시에서 다른 도시로 가는 일방통행 제트기 항공편과 그 요금을 나타내는 세 정수 $J_i$, $K_i$, $T_i$가 공백으로 구분되어 주어집니다.

• 첫째 줄: 규칙을 지키면서 벌 수 있는 최대 금액을 나타내는 정수 하나. 벌 수 있는 금액에 한계가 없다면 $-1$을 출력하세요.

예시의 세계에는 다섯 개의 도시, 세 개의 도로, 두 개의 제트기 노선이 있습니다. 베시는 도시 $1$에서 출발하며, 각 도시에서 다른 곳으로 이동하기 전까지 최대 $100$달러만 벌 수 있습니다.

베시는 도시 $1 \to$ 도시 $5 \to$ 도시 $2 \to$ 도시 $3$의 순서로 이동하여 총 $4 \times 100 - 150 = 250$ 달러를 벌 수 있습니다.