과세 대상 도로 구간

정부는 탈린과 타르투를 잇는 간선도로의 일부 구간에 통행료를 매기려고 한다. 운전자는 가능하면 통행료가 붙은 구간을 피하고, 옆길이 더 싸면 그쪽으로 돌아간다. 비용이 같으면 운전자는 언제나 간선도로를 고른다.

차가 마을을 통과하기 시작하면 주민들이 크게 반발하고, 그 결과 정부가 무너질 수도 있다. 정부는 주민의 반발을 피하면서 통행료 수입을 최대한 늘리고 싶어 한다.

간선도로 위 임의의 지점에서 출발해 도착하는 운전자가 간선도로만 이용하는 것이 최적이 되도록, 정부가 간선도로 구간들에 매길 수 있는 금액의 최댓값을 구하라.

이미 알려진 사실은 다음과 같다. 간선도로의 두 끝점 사이에는 옆길을 이용하면서 간선도로보다 비용이 적은 경로가 없다. 또한 간선도로의 각 구간은 다른 도로 구간을 이용해 피할 수 있으므로, 어떤 구간의 가격도 무한정 올릴 수는 없다.

첫 줄에 네 정수 $K$, $R$, $T$, $T\_P$가 주어진다.

• $K$는 1킬로미터당 연료비(센트)이다 ($1 \le K \le 100$).
• $R$은 도로망의 교차로 수이다 ($2 \le R \le 5\,000$). 교차로는 $0 \dots R-1$로 번호가 매겨져 있다.
• $T$는 교차로 사이의 도로 구간 수이다 ($2 \le T \le 15\,000$).
• $T\_P$는 간선도로의 구간 수이다 ($1 \le T\_P \le 1\,000$).

이어지는 $T$개의 줄에는 각각 정수 $R_1$, $R_2$, $P$가 주어진다. 이는 교차로 $R_1$과 $R_2$가 길이 $P$킬로미터의 도로 구간으로 연결되어 있다는 뜻이다 ($0 < P \le 5\,000$). 간선도로는 교차로 $0 \dots T\_P$를 번호가 증가하는 순서로 지나며, 간선도로의 구간들은 입력에서 간선도로에 나타나는 순서대로 가장 먼저 주어진다.

과세되는 구간들의 가격 합계를 나타내는 정수 하나를 텍스트 파일에 출력한다.