대피소

어두운 방에서 밀란이 세 다리 탁자에 앉아 약 23시 55분에 핵재난이 도시에 미칠 수 있는 결과를 생각하고 있다. 밀란은 시장이므로 관련 사실을 잘 알고 있다.

도시에는 정확히 $N$명의 주민이 살고, 각 주민은 자기 집에 산다. 정확히 $M$쌍의 집 사이에는 도로가 있고, 각 도로를 지나는 데 걸리는 시간이 주어진다. 정확히 $K$개의 집에는 원자 대피소가 있으며, 각 대피소에 들어갈 수 있는 인원이 주어진다. 밀란은 "이 도시의 모든 주민을 대피시키는 데 필요한 최소 시간은 얼마인가?"라는 질문에 골몰하고 있다.

대피는 모든 주민이 어떤 원자 대피소에든 들어가는 것을 뜻한다. 주민은 최적으로(최단 경로로) 이동하며, 한 도로 위에서는 서로 다른 방향으로 여러 사람이 동시에 움직일 수 있다고 가정한다. 또한 임의의 두 집 사이에는 주어진 도로의 일부를 이용하는 경로가 적어도 하나 있다고 가정한다.

첫 줄에 자연수 $N$($1 \le N \le 100000$), $M$($1 \le M \le 300000$), $K$($1 \le K \le 17$)가 주어진다. 각각 주민 수, 도로 수, 대피소 수이다. 집은 1번부터 $N$번까지 번호가 매겨져 있다.

이어지는 $M$개 줄에는 자연수 $A$, $B$($1 \le A, B \le N$, $A \ne B$)와 $C$($1 \le C \le 10^9$)가 주어진다. 이는 $A$번 집과 $B$번 집 사이에 도로가 있고, 이를 지나는 데 $C$의 시간이 걸린다는 뜻이다.

이어지는 $K$개 줄에는 자연수 $X$($1 \le X \le N$)와 $Y$($1 \le Y \le 10^9$)가 주어진다. 이는 $X$번 집에 원자 대피소가 있고, 최대 $Y$명까지 수용할 수 있다는 뜻이다. 모든 대피소의 수용 인원 합은 $N$ 이상이다.

모든 주민을 대피시키는 데 필요한 최소 시간을 한 줄에 출력한다.

첫 번째 예제에서 3단위 시간이면 1, 2, 3번 집의 사람들은 1번 집의 대피소로 갈 수 있고, 4번과 5번 집의 사람들은 4번 집의 대피소로 갈 수 있다. 4번 집의 대피소는 최대 2명만 받으므로 그보다 짧은 시간에는 모든 사람이 대피소에 도착할 수 없다.