Ngọt - LẦN CUỐI (đi bên em xót xa người ơi)

Trong lần cuối đi bên nhau, bạn và người ấy đang ở một thành phố gồm $n$ con phố. Các con phố này được liên kết với nhau bằng $m$ con đường hai chiều (lưu ý không thoả mãn là tất cả thành phố sẽ luôn đi được tới nhau bằng những con đường) và tất nhiên, các con đường này có thời gian đi là khác nhau (mỗi con đường sẽ có $3$ dữ liệu $u,\ v,\ w$ lần lượt là hai con phố ở đầu của con đường và thời gian để đi qua con đường đó). Ngoài ra, ở một số con phố người ta lắp đặt $k$ trạm dịch chuyển với trạm dịch chuyển thứ $i$ thì nó sẽ đặt ở con phố $p_i$ và có thời gian khởi tạo là $t_i$. Để dịch chuyển giữa hai trạm dịch chuyển $i$ và $j$ thì ta sẽ tốn thời gian khởi tạo cả hai trạm $i$ và $j$ hay nói cách khác ta tốn $t_i\ +\ t_j$ đơn vị thời gian.

Bạn đang ở con phố $1$ và muốn đưa người ấy về nhà ở con phố $n$, tính thời gian nhỏ nhất có thể đạt được, nếu không thể đưa người ấy về nhà, in ra $-1$.

Input

• Dòng đầu tiên gồm $3$ số $n,\ m,\ k$ lần lượt là số lượng con phố trong thành phố, số con đường hai chiều và số trạm dịch chuyển. $(1\leq k\leq n\leq 2.10^5,\ 0\leq m\leq min(\frac{n.(n-1)}{2},\ 2.10^5))$
• $m$ dòng tiếp theo mỗi dòng chứa $3$ số $u_i,\ v_i,\ w_i$ là dữ liệu của con đường thứ $i$ (dữ liệu đảm bảo không có nhiều hơn $1$ con đường trực tiếp giữa hai con phố). $(1\leq u_i,\ v_i\leq n,\ 0\leq w_i\leq 10^9,\ u_i \ne v_i)$
• $k$ dòng tiếp theo mỗi dòng chứa $2$ số $p_i$ và $t_i$ là dữ liệu của cổng dịch chuyển thứ $i$. $(1\leq p_i\leq n, 0\leq t_i\leq 10^9)$

Output

• Gồm một dòng duy nhất chứa thời gian ngắn nhất có thể đạt được, nếu không thể đi tới $n$ in $-1$.

Subtasks

• Subtask $1$: Đảm bảo $k = 2$ và $m = 0$. ($1$ điểm)
• Subtask $2$: Đảm bảo $n\leq 5.10^3$. ($5$ điểm)
• Subtask $3$: Đảm bảo $k\leq 10$. ($14$ điểm)
• Subtask $4$: Không có ràng buộc gì thêm. ($80$ điểm)

Example

4 3 2
1 2 6
2 4 4
1 4 9
1 4
4 4

8

4 1 2
1 2 10
3 10
4 1

-1