빨간 모자

통과하기 힘든 숲에 $N$개의 공터와 $M$개의 오솔길이 있다. 각 오솔길은 서로 다른 두 공터를 잇는다. 두 공터는 여러 개의 오솔길로 연결될 수 있다.

빨간 모자와 할머니는 서로 다른 두 공터에 산다. 빨간 모자의 집은 $1$번 공터에, 할머니의 집은 $N$번 공터에 있다. 빨간 모자는 숲을 잘 알아서 각 오솔길을 지나는 데 걸리는 최소 시간을 알고 있다. 빨간 모자는 공터에서만 오솔길을 갈아탄다. 각 공터에는 빨간 모자가 잠시 숨을 수 있는 은신처가 있다.

같은 숲에 늑대도 산다. 늑대가 오솔길을 달리는 시간은 빨간 모자가 같은 오솔길을 걷는 시간과 다를 수 있다. 늑대가 같은 오솔길을 여러 번 달리면, 매번 걸리는 시간이 다를 수도 있다.

빨간 모자가 할머니에게 파이를 가져다주려고 집을 나서는 모습을 공터 끝에서 본 늑대는, 빨간 모자가 집을 나서기로 한 순간부터 늘 다니던 길을 따라 집에서 할머니 집까지 달리기 시작했다. 늑대의 경로는 할머니 집 공터에 도착하는 순간 끝난다. 늑대는 어떤 공터에서도 멈추지 않는다.

할머니를 무사히 만나려면 빨간 모자가 늑대를 앞질러야 한다. 이때 빨간 모자는 늑대와 같은 오솔길 위에 있을 수 없다. 늑대가 막 오솔길을 떠나는데 빨간 모자가 그 오솔길에 막 들어서는 경우, 또는 그 반대의 경우도 포함한다. 공터에서 늑대와 마주치지 않으려고 빨간 모자는 그곳의 은신처를 이용한다. 빨간 모자는 늑대와 동시에 공터에 들어설 수 없고, 늑대가 공터에 들어서는 순간에 은신처를 떠날 수 없다. 필요하면 빨간 모자는 최소 시간보다 오래 걸려 오솔길을 걸을 수 있고, 처음 정한 것보다 늦게 집을 나설 수도 있다.

늑대가 달린 오솔길의 순서가 주어졌을 때, 빨간 모자가 늑대보다 먼저 할머니 집에 도착하도록 돕는 프로그램을 작성한다.

첫 줄에 세 정수 $N$, $M$, $K$가 주어진다 ($2 \le N \le 2\,000$, $1 \le M \le 100\,000$, $1 \le K \le 100\,000$). 다음 $M$개 줄에는 세 정수 $B_i$, $E_i$, $T_i$가 주어진다. $B_i$와 $E_i$는 $i$번 오솔길이 잇는 공터 번호이고, $T_i$는 빨간 모자가 그 오솔길을 걷는 데 필요한 최소 시간이다 ($1 \le T_i \le 10\,000$).

다음 $K$개 줄에는 두 정수 $P_i$와 $V_i$가 주어진다. $P_i$는 늑대가 달리는 오솔길의 번호이고, $V_i$는 늑대가 그 오솔길을 달리는 데 걸리는 시간이다 ($1 \le V_i \le 10\,000$). 늑대의 경로는 항상 $1$번 공터에서 시작해 $N$번 공터에서 끝난다.

입력의 모든 수는 정수이며, 같은 줄의 수는 공백으로 구분된다.

빨간 모자가 늑대보다 빨리 할머니 집에 도착할 수 없다면 NO를 출력한다.

빨리 도착할 수 있다면 첫 줄에 YES를 출력한다. 둘째 줄에는 빨간 모자의 경로에 있는 오솔길의 개수를 출력한다. 셋째 줄에는 빨간 모자가 지나가는 순서대로 오솔길의 번호를 공백으로 구분해 출력한다. 오솔길을 지나는 시간이나 공터에서 머문 시간은 출력하지 않는다.