题目背景

译自 Izborne Pripreme 2019 (Croatian IOI/CEOI Team Selection) D2T2。$\texttt{4s,0.5G}$。

题目描述

给定 $N$ 个点 $M$ 条边的无向连通图，边有边权。有 $K$ 个关键点 $A_1,A_2,\cdots,A_K$，容量为 $S_1,S_2,\cdots,S_K$。

图中的居民要疏散。也就是说，你需要构造一个序列 $B_1,B_2,\cdots,B_N$，使得：

• $\forall 1\le i\le N$，$1\le B_i\le K$；
• 对于 $1\le i\le K$，定义 $\displaystyle \mathrm{cnt}_i=\sum_{1\le j\le N} [B_j=i]$，也就是 $i$ 在 $B$ 序列中出现的次数。则 $\mathrm{cnt}_i\le S_i$。

定义序列 $B$ 的疏散时间为 $\displaystyle \max_{1\le i\le N} \operatorname{dist}(i,A_{B_i})$，其中 $\operatorname{dist}(u,v)$ 指图中 $u,v$ 间最短路的长度。

求出疏散时间的最小值。保证 $\sum_i S_i\ge N$。

输入格式

第一行，三个正整数 $N,M,K$；

接下来 $M$ 行，每行三个正整数 $u,v,w$，描述一条无向边 $(u,v)$，边权为 $w$。保证 $u\neq v$。

接下来 $K$ 行，每行两个正整数描述 $A_i,S_i$。

保证 $\sum_i S_i\ge N$。

输出格式

输出一行一个数，表示答案。

5 5 2
1 2 1
1 3 3
2 3 4
3 4 1
4 5 1
1 10
4 2

3

7 8 3
1 2 5
2 3 3
3 4 5
1 4 1
4 5 7
5 6 2
6 7 1
4 7 4
3 3
7 3
6 2

5

提示

对于 $100\%$ 的数据，保证：

• $1\le N\le 10^5$；
• $N-1\le M\le 3\times 10^5$；
• $1\le K\le 17$；
• 给定图连通，无自环；
• $1\le w,S_i\le 10^9$；
• $1\le u,v,A_i\le N$；
• $S_i$ 两两不同；
• $\sum_i S_i\ge N$。