OI题库

当前，随着经济的深入变革，我们的社会环境也得到了很大改善，在中国，城市人口每年以7%的速度增长，一些大城市的人口增长速度更是快的惊人，一个显而易见的例子是：今天的上海每小时新增加10所住宅和100平方米的公路，已率先成为世界大都市。
由于人口和城市面积的急剧增长，公共交通成为一个重要的问题，于是大量的十字路口遍步整个城市。
举个例子，以前广州海珠区有N个自然村，有一些道路把这些村子连接起来，使得任意两个村子都存在一条路径相通，任意两条路只在某个村子那里相交。简单来说，海珠区可以被视为一棵树，村子是结点，路为边，海珠区政府就位于树的根结点所在的村子。这棵树有M个叶子结点（L[1],...,L[M]，换言之，这M个村子中的每一个都只与一个村子直接相连），其它(N-M)个结点（包括根结点）每一个结点都至少有两个子结点，如下图1所示。
近年来，又新建了一条环状交叉路穿过了这M个村子（L[1],...,L[M]），如图2所示：

图1                                                            图2
假定L[0]是一个离海珠区很远的邮局，但也在环路上。邮递员想以尽可能快的速度往各个村子送EMS，从统计数据中你可得知邮递员走每条路需花费的时间，现在邮局局长想知道是否存在一个环（L[0]→L[1]→...→L[M]→L[0]），使得邮递员只需访问这N个村子中的每个村子一次，如果可行，输出完成这个任务所花费的最小时间，否则只需输出“-1”（双引号不需输出）。

【输入格式】

输入数据有两部分组成：
第一部分的第一行是一个正整数N（3≤N≤1000），表示村子的个数，接下来有N-1行，第i行有三个正整数Xi(1≤Xi≤N),Yi(1≤Yi≤N),Ti(0< Ti≤1000)，用来描述第i条边，其中Yi为树中Xi的父结点，Ti表示从Xi到Yi或者从Yi到Xi所需的时间。
第二部分的第一行是一个正整数M（1≤M< N），表示叶子结点的个数，接下来有M+1行，表示交叉路，第i(0≤i≤M)行有三个非负整数L[i](0≤L[i]≤N),L[i+1](0≤L[i+1]≤N),Ci(0< Ci≤1000)，假定L[0]=L[M+1]=0，交叉路是一个环L[0]→L[1]→L[2]→...→L[M]→L[M+1]，Ci表示从L[i]到L[i+1]或者从L[i+1]到L[i]所需的时间。

【输出格式】

【输入样例】

输入文件名：exists.in

3
2 1 1
3 1 1

2
0 2 1
2 3 1
3 0 1

输出文件名：exists.out

4

提示：可行的环为0→2→1→3→0，总的时间为4，如下图：