Description

曹妃甸的气温是非常潮湿闷热的，并且宿舍里还没有空调，为了给学生创建一个更好的环境，学校决定把曹妃甸校区拆了重建。

学校已经把主要的建筑规划好了，现在需要请你来规划一下校园的路线，因为学校很穷，所以设计的路线只需要保证学校的主要建筑之间是联通的就好，并且要让所建的总路程尽可能的短，学校最大能承受的总路程修建距离为k(千米) ，学校规划了 n 个主要建筑 ， 通过招标收到了 m 个承建的方案 ，每份承建方案里包含 承建连接的两个建筑名 a , b ，路段长度 c（千米） 。如果能找出合适的方案，输出"YES"并输出最短的承建路程长度。如果找不出合适的方案，输出"NO"。

Input Format

第一行有三个数 k , n , m 。k为学校最大能承受的总路程修建距离，n为学校规划的主要建筑数，m表示承接方案的个数。

$( k ≤ 2 \times 10^{12} , m ≤ 2 \times 10^5, n ≤ 5 \times 10^2)$

接下来n行，每行一个字符串表示主要建筑的名称

第n + 2 行到 n + m + 2 行 每行两个字符串 a , b 和一个整数c ,分别表示承建连接的两个建筑名，路段长度。

(c ≤ 2 × 105** ** )

Output Format

第一行输出"YES" or "NO"，表示是否能建成

如果能建成，第二行返回最短路程长度。(KM)

40 5 6
zhu
lan
mei
store
teach
store zhu 3
zhu mei 6 
zhu lan 5
lan teach 1 
lan mei 3
teach mei 10​

YES
12​

Hint

根据上图的主要建筑我们建立了一个完全图。

他所生成的最小二叉树为 下图所示。

所需要的权值为 3 + 1 + 5 + 3 = 12 km

Source

Prim 最短路 最小生成树 并查集 Kruskal