T607256 造地铁©shutdown,2025

shutdown今天十分无聊，他又双叒叕$\texttt{叕}^叕$要去造地铁。

存档地铁规划图里有$m$条地铁线路，$p$个区间。 表示$i$,$j$两个地铁站的距离称作($i$,$j$)。 每一条线路都有 一个修建难度值$v$。 每一个区间都属于一条1条地铁线路$x$。 对于每一个区间，它的修建耗力等于它的长度$l$加上这条区间属于的地铁线路的修建难度。 #### 提示：不一定每两个地铁站之间都会有区间,但是题目保证所有地铁站可以组成一个连通块 现在，shutdown给每一条地铁线路都规定好了起点站($start$)和终点站($end$)。 shutdown想问(diao)问(nan)你,修建所有的地铁线路（要求所有地铁站都有地铁连接）所需耗费的耗力值至少是多少？

第一行输入两个整数$p,m$。 接下来$m$行每行输入两个整数$z,v$两个字符串$start,end$代表$z$号线的起点站是$start$,终点站是$end$，修建难度值是$v$。 在接下来$p$行每行输入两个整数$l,x$和两个字符串$i,j$代表从$i$站到$j$站的长为$l$的区间属于$x$号线。

输出一个整数$cnt$代表最小耗力值是多少。

1