关于自动驾驶汽车的路径规划的问题

【题目描述】

一个自动驾驶的汽车，其只能按照调度系统到指定的景点停车场进行充电，每个

景点中间的路上，都会有一些游客上车前往下一个景点。调度系统会告诉自动驾驶

汽车，到哪个景点的停车场上充电，但具体走那条路到该停车场充电没有限制，但

是自动驾驶汽车在每次行进过程中，不能重复到达同一个景点。请设计算法，给出

从景点 a 到景点 b 进行充电，再返还景点 a，这个自动驾驶汽车如何规划行进线路（线

路上不能到达同一个景点多次），使得沿途接上的游客数量是最多的，并输出最多

的上车的游客数量。

【输入格式】

第一行有两个数：n 和 m，其中 n 表示景点的数量，m 是景点间的单行道数量。

第二行到第 m+1 行，有三个整数：第一个数是起始景点的编号，第二个数是该路

径终点景点的编号，第三个数是从起点到终点，需要乘车的人数。

第 m+2 行，有两个数字，第一个数字是自动驾驶汽车的出发景点，第二数字是中

间进行充电的景点编号。

【输出格式】

一个数，表示该自动驾驶汽车往返一次，可以接送最多多少人。

【样例输入】（测试数据不包含本样例）

3 5

1 2 4

2 1 6

1 3 11

3 1 3

2 3 2

1 2

【样例输出】

10