Fine Dining

긴 하루를 마치고 소들이 헛간으로 돌아간다. 모두 지치고 배고픈 상태다.

농장에는 $N$개의 목초지가 있고 ($2 \leq N \leq 50,000$), 편의상 $1 \dots N$번이 붙어 있다. 소들은 모두 $N$번 목초지에 있는 헛간으로 가려고 한다. 나머지 $N-1$개의 목초지에는 각각 소 한 마리가 있다. 소들은 $M$개의 무방향 길 ($1 \leq M \leq 100,000$)을 통해 목초지 사이를 이동할 수 있다. $i$번째 길은 목초지 $a\_i$와 $b\_i$를 연결하며, 지나는 데 $t\_i$의 시간이 걸린다. 모든 소는 길을 따라 헛간에 도달할 수 있다.

배가 고픈 소들은 집으로 가는 길에 멈춰서 먹을 것을 찾는 데 관심이 있다. 마침 $K$개의 목초지에 맛있는 건초 더미가 있으며 ($1 \leq K \leq N$), $i$번째 건초 더미의 맛있는 정도는 $y\_i$이다. 각 소는 헛간으로 가는 도중에 건초 더미 하나에 멈출 용의가 있지만, 그 건초 더미를 방문해서 경로에 추가되는 시간이 그 건초 더미의 맛있는 정도 이하일 때만 그렇게 한다. 소는 식사를 위해 많아야 하나의 건초 더미를 "공식적으로" 방문한다. 건초 더미가 있는 다른 목초지를 경로가 지나가더라도 괜찮으며, 그때는 그냥 무시한다.

첫째 줄에는 공백으로 구분된 세 정수 $N$, $M$, $K$가 주어진다. 다음 $M$개의 줄에는 각각 세 정수 $a\_i$, $b\_i$, $t\_i$가 주어지며, 이는 목초지 $a\_i$와 $b\_i$를 연결하고 지나는 데 $t\_i$의 시간이 걸리는 길을 나타낸다 ($a\_i$와 $b\_i$는 서로 다르고, $t\_i$는 $10^4$ 이하의 양의 정수이다).

그다음 $K$개의 줄에는 각각 건초 더미를 나타내는 두 정수가 주어진다. 건초 더미가 있는 목초지의 번호와 그 건초 더미의 맛있는 정도 (최대 $10^9$인 양의 정수)이다. 여러 건초 더미가 같은 목초지에 있을 수 있다.

출력은 $N-1$개의 줄로 이루어진다. $i$번째 줄에는 목초지 $i$에 있는 소가 헛간으로 가는 길에 건초 더미를 방문해서 먹을 수 있으면 정수 $1$, 그렇지 않으면 $0$을 출력한다.

이 예에서 목초지 3에 있는 소는 식사를 위해 멈춰야 한다. 경로가 2에서 8로 6만 늘어나는데, 이 증가량이 건초 더미의 맛있는 정도 7 이하이기 때문이다. 목초지 2에 있는 소는 목초지 2의 건초를 먹는 게 당연하다. 최적 경로에 아무 변화가 없기 때문이다.

목초지 1에 있는 소는 흥미로운 경우다. 얼핏 보면 이 소의 최적 경로 (길이 10)는 건초를 먹으려고 멈추기에는 너무 많이 늘어날 것 같다. 하지만 실제로는 건초에 멈추는 것이 이득인 경로가 있다. 목초지 4로 이동한 뒤 목초지 2로 가서 (건초를 먹고) 다시 목초지 4로 돌아오는 것이다.