Sau một ngày dài, những cô bò đang trở về chuồng, vừa mệt vừa đói.

Trang trại gồm \(N\) đồng cỏ (\(2 \leq N \leq 50,000\)), được đánh số thuận tiện từ \(1 \dots N\). Tất cả các cô bò đều muốn đi đến chuồng ở đồng cỏ \(N\). Mỗi đồng cỏ trong số \(N-1\) đồng cỏ còn lại có một cô bò. Các cô bò có thể di chuyển giữa các đồng cỏ qua một tập hợp gồm \(M\) đường mòn hai chiều (\(1 \leq M \leq 100,000\)). Đường mòn thứ \(i\) nối hai đồng cỏ \(a_i\) và \(b_i\), đồng thời mất \(t_i\) đơn vị thời gian để đi qua. Mọi cô bò đều có thể đến chuồng qua một dãy đường mòn.

Vì đang đói, các cô bò muốn cân nhắc dừng lại ăn trên đường về. Thật tiện lợi, \(K\) đồng cỏ có những kiện cỏ khô thơm ngon (\(1 \leq K \leq N\)), trong đó kiện cỏ khô thứ \(i\) có độ ngon \(y_i\). Mỗi cô bò sẵn sàng dừng lại tại một kiện cỏ khô duy nhất trên đường đến chuồng, nhưng chỉ khi thời gian tăng thêm trên lộ trình của cô không vượt quá độ ngon của kiện cỏ khô mà cô ghé ăn. Lưu ý rằng mỗi cô bò chỉ "chính thức" ghé nhiều nhất một kiện cỏ khô để ăn, dù lộ trình của cô có thể đi qua những đồng cỏ khác cũng có kiện cỏ khô; cô chỉ đơn giản là bỏ qua chúng.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(K\) cách nhau bởi dấu cách. Mỗi dòng trong \(M\) dòng tiếp theo chứa ba số nguyên \(a_i\), \(b_i\) và \(t_i\), mô tả một đường mòn giữa hai đồng cỏ \(a_i\) và \(b_i\) cần \(t_i\) đơn vị thời gian để đi qua (\(a_i\) và \(b_i\) khác nhau, còn \(t_i\) là số nguyên dương không vượt quá \(10^4\)).

\(K\) dòng tiếp theo, mỗi dòng mô tả một kiện cỏ khô bằng hai số nguyên: chỉ số của đồng cỏ chứa nó và độ ngon của nó (một số nguyên dương không vượt quá \(10^9\)). Một đồng cỏ có thể chứa nhiều kiện cỏ khô.

Dữ liệu ra

Dữ liệu ra gồm \(N-1\) dòng. Dòng \(i\) chứa số nguyên duy nhất \(1\) nếu cô bò ở đồng cỏ \(i\) có thể ghé và ăn một kiện cỏ khô trên đường đến chuồng, và chứa \(0\) nếu không thể.

Ví dụ

4 5 1
1 4 10
2 1 20
4 2 3
2 3 5
4 3 2
2 7

1
1
1

Nguồn

Đề bài gốc: USACO 2018 December Contest, Gold — Fine Dining

Tác giả: Dhruv Rohatgi