사탕 공헌

여행 중에 복권에 당첨되었다. 그런데 이 복권의 1등 상금은 현금이 아니라 사탕이었다! 이제 집으로 가져가야 할 사탕 더미가 생겼다. 다행히 트럭을 구할 수 있었으니, 이제 집으로 운전만 하면 된다.

트럭에 이렇게 많은 사탕을 싣고 한 나라에서 다른 나라로 가려면 세금을 내야 한다. 모두가 사탕을 좋아하므로, 이 세금을 사탕으로 낼 수 있다.

인터넷을 조금 뒤져서, 트럭으로 건널 수 있는 국경과 각 국경을 건널 때 내야 하는 세금 비율이 적힌 목록을 찾았다. 사탕을 소수로 낼 수 없고 사탕이 꽤 맛있으므로, 세관은 항상 올림한다. 국경을 넘어 가져가는 사탕 수에 대해서만 세금을 내면 된다.

집에 가져갈 수 있는 사탕의 최대 개수는 얼마인가?

입력은 다음과 같다.

• 한 줄에 정수 $n$ ($2\leq n\leq 1\cdot 10^5$), $m$ ($1 \leq m \leq 2\cdot 10^5$)이 주어진다. $n$은 나라의 수, $m$은 국경의 수이다.
• 한 줄에 세 정수 $s$ ($1\leq s\leq n$), $t$ ($1 \leq t \leq n$, $t\neq s$), $c$ ($1\leq c \leq 10^9$)가 주어진다. $s$는 복권에 당첨된 나라, $t$는 집이 있는 나라, $c$는 복권에서 얻은 사탕의 수이다.
• 그다음 $m$개의 줄에 세 정수 $u, v$ ($1\leq u, v \leq n$, $u\neq v$)와 $p$ ($0 \leq p \leq 100$)가 주어진다. $p$는 나라 $u$에서 $v$로, 또는 그 반대로 갈 때 내야 하는 세금의 비율이다.

트럭을 타고 집에 갈 수 있고, 각 나라 쌍은 많아야 한 번만 주어진다.

집에 도착했을 때 가져갈 수 있는 사탕의 최대 개수를 출력한다.