Problem1375--PIPI的逃跑路线Ⅱ

1375: PIPI的逃跑路线Ⅱ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 100  Solved: 12
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI终于暂时躲过POPO的追杀了,但是残血状态的他必须前往n个城市采集补血材料。
已知这n个城市编号为1到n,总共有n-1条道路,PIPI可以从这n个城市中选择一个起始城市出发采集补血材料,但是PIPI只能从一些特定城市出发。
请问PIPI采集完补血材料所需要走的最短路程。

Input

第一行一个正整数n,n<=10^5。
接下来n-1行,每行三个正整数x,y,w,表示x号城市与y号城市之间有一条距离为w的道路,其中x,y<=n,w<=10^4。
接下来一行有n个数,表示1到n号城市的状态,0表示不可以从这个城市出发,1表示可以从这个城市出发。

Output

输出PIPI采集完补血材料的最短路程。
若PIPI无法采集完补血材料,输出-1。

Sample Input

10
6 3 3776
6 5 7270
5 1 6131
5 9 1451
3 2 7237
9 4 4559
9 8 1045
3 7 1699
4 10 8052
1 1 1 1 1 1 0 1 0 1

Sample Output

50095

Source/Category

中等