Little Red Riding Hood

An impassable forest has $N$ clearings and $M$ paths between them. Each path connects two different clearings. Two clearings may be connected by several paths.

Little Red Riding Hood and her grandmother live in two different clearings. Red's house is in clearing $1$, and the grandmother's house is in clearing $N$. Red knows the minimum time she needs to walk each path. She switches from one path to another only at clearings. Every clearing has a shelter where Red can hide for some time.

A Wolf also lives in this forest. The time the Wolf takes to run along a path may differ from the time Red takes on the same path. If the Wolf runs the same path several times, each run may take a different amount of time.

The Wolf saw Red at the edge of her clearing as she set out to bring pies to her grandmother. He started running along the usual route from Red's house to the grandmother's house at the moment she decided to leave. His route ends as soon as he reaches the grandmother's clearing. The Wolf never stops at any clearing.

To find her grandmother safe, Red must overtake the Wolf. She may never be on the same path as the Wolf, even if the Wolf is just leaving the path while she is just entering it, or the reverse. To avoid meeting the Wolf at a clearing, Red uses the shelter there. Red may not enter a clearing at the same time as the Wolf, and she may not leave a shelter at the moment the Wolf enters that clearing. If needed, Red may take a path longer than the minimum time, and she may leave home later than she first planned.

Write a program that helps Red reach her grandmother before the Wolf, given the sequence of paths the Wolf runs.

The first line contains three integers $N$, $M$, and $K$ ($2 \le N \le 2\,000$, $1 \le M \le 100\,000$, $1 \le K \le 100\,000$). Each of the next $M$ lines contains three integers $B_i$, $E_i$, and $T_i$, where $B_i$ and $E_i$ are the clearings connected by the $i$-th path, and $T_i$ is the minimum time Red needs to walk it ($1 \le T_i \le 10\,000$).

Each of the next $K$ lines contains two integers $P_i$ and $V_i$. $P_i$ is the number of the path the Wolf runs along, and $V_i$ is the time he spends on it ($1 \le V_i \le 10\,000$). The Wolf's route always starts at clearing $1$ and ends at clearing $N$.

All numbers in the input are integers, and numbers on the same line are separated by spaces.

If Red cannot reach her grandmother's house faster than the Wolf, print NO.

If Red can reach it faster than the Wolf, print YES on the first line. On the second line, print the number of paths in Red's route. On the third line, print the numbers of the paths in the order Red walks them, separated by spaces. Do not print the travel times on the paths or the times spent at clearings.