题目描述

快递公司每日早晨，给每位快递员推送需要送到客户手中的快递以及路线信息，快递员自己又查找了一些客户与客户之间的路线距离信息，请你依据这些信息，给快递员设计一条最例短路径， 告诉他最短路径的距离。

注意：

1. 不限制快递包裹送到客户手中的顺序，但必须保证都送到客户手中
2. 用例保证一定存在投递站到每位客户之间的路线，但不保证客户与客户之间有路线，客户位置及投递站均允许多次经过。
3. 所有快递送完后，快递员需回到投递站

输入描述

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

接下面n行，输入快递公司发布的客户快递信息， 格式为：客户id 投递站到客户之间的距离distance

再接下来的m行，是快递员自行查找的客户与客户之间的距离信息， 格式为：客户1id 客户2id distance

在每行数据中，数据与数据之间均以单个空格分割

规格; 0 < n <=10 0 <= m <= 10 0< 客户id <= 1000 0< distance <= 10000

输出描述

最短路径距离，如无法找到，请输出 -1

用例1

输入

2 1
1 1000
2 1200
1 2 300

输出

2500

说明

路径1： 快递员先把快递送到客户1手中，接下来直接走客户1到客户2之间的直通路线，最后走投递站与客户2之间的路，回到投递站，距离为1000 + 300 + 1200 = 2500 路径2： 快递员先把快递送到客户1手中，接下来回快递站，再出发把客户2的快递送到，在返回到快递站，距离为：1000 + 1000 + 1200 + 1200 = 4400

路径3：快递员先把快递送到客户2手中，接下来直接走客户2到客户1之间的直通线路，最后走投递站和客户1之间的路，回到投递站，距离为1200 + 300 + 1000 =2500

其他路径……

所有路径中，最短路径距离为2500

用例2

输入

5  1
5 1000
9 1200
17 300
132 700
500 2300
5 9 400

输出

9200

说明：在所有可行的路径中，最短路径长度为1000 + 400 + 1200 + 300 + 300 + 700 + 700 + 2300 + 2300 = 9200

Java

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取客户数量和路线数量
        int n = scanner.nextInt();
        int r = scanner.nextInt();