Tolled Road Segments

The government plans to charge a toll on some segments of the main highway between Tallinn and Tartu. Drivers try to avoid tolled segments whenever they can, so they take a side road around a toll if it is cheaper. When the costs are equal, a driver always prefers the main highway.

If cars start driving through local villages, residents will be very angry, and the government could fall. The government wants the largest possible toll revenue while avoiding that anger.

Find the largest total amount the government can charge on the segments of the main highway, so that a driver who starts and ends at any point on the main highway finds it optimal to drive only along the main highway.

It is known that the main highway is already optimal: no route between its endpoints that uses a side road is cheaper than the route along the main highway. It is also known that every single main highway segment can be avoided using other road segments, so no segment's price can be raised without limit.

The first line contains four integers $K$, $R$, $T$, and $T\_P$, where:

• $K$ is the fuel cost per kilometer in cents ($1 \le K \le 100$).
• $R$ is the number of junctions in the road network ($2 \le R \le 5\,000$). The junctions are numbered $0 \dots R-1$.
• $T$ is the number of road segments between the junctions ($2 \le T \le 15\,000$).
• $T\_P$ is the number of segments on the main highway ($1 \le T\_P \le 1\,000$).

Each of the next $T$ lines contains three integers $R_1$, $R_2$, and $P$. They mean that junctions $R_1$ and $R_2$ are connected by a road segment of length $P$ kilometers ($0 < P \le 5\,000$). The main highway passes junctions $0 \dots T\_P$ in increasing order of their numbers, and its segments are the first ones listed in the input, in the order they appear on the highway.

Print one integer to the text file: the total price of all taxed segments.