4600: 【最短路问题】2024D-快递员的烦恼

金币值:1 Time Limit:4.000 s Memory Limit:128 M
Solved:49 Submit:139 正确率:35.25% Creator:

Description

快递公司每日早晨,给每位快递员推送需要送到客户手中的快递以及路线信息。

快递员自己又查找了一些客户与客户之间的路线距离信息,请你依据这些信息,给快递员提供一条最短路线图,保证使快递员路程的总距离最短。 


注意: 

1. 不限制快递员送快递到客户手中的顺序,但必须保证最终到客户手中 

2. 用例保证一定存在快递员从快递站点送到客户之间的距离,但不保证客户与客户之间的距离。客户位置及快递站均为允许多次经过 

3. 所有快递送完后,快递员需回到快递站

Input

首行输入两个正整数 n, m 

接下来 n 行,每行输入 2 个整数快递信息,格式为:客户 id 快递送到客户手中的距离 distance 

再接下来 m 行,每行输入 3 个整数客户之间的距离信息,格式为:客户 id1 客户 id2 两个客户之间的距离 distance 

在行末有换行符。数据保证输入均为以换行符隔开的整数。

Output

最短路径距离,如无法找到则输出 -1

Sample Input    Copy

2 1
1 1000
2 1200
1 2 300

Sample Output    Copy

2500

HINT

0 < n <= 10 

0 < m <= 10 

0 <= 客户 id <= 1000 

0 < distance <= 10000