1234: 任意点对最短路

Time Limit: 1 Sec Memory Limit: 128 MB

Submission：111 AC：38 Score：100.00

给出一个无向图，请输出任意两个点之间的最短路径长度。

第一行包含三个整数N、M，分别表示点的个数、边的个数；

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条边的两个点和长度；

接下来输入一个数字Q，表示询问的个数，对于每一询问，输入两个点的编号，输入这两个点之间的最短路径。

输出包括Q行，每行为一个询问的答案，每个点到自己的距离为0，如果两个点之间不连通，请输出-1.

input:

4 6 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4 5 1 3 2 4 2 3 4 2 4 1

output:

4 1 2 1 3

对于100%的数据：N<=1000，Q<=1000