5958: 【宽搜】派发巧克力

情人节到了，约翰准备向奶牛派发巧克力。约翰的牧场有N块草地（这些草地的编号为1到N），有M条双向道路将它们连接起来，第i条道路连接的草地为R_i和S_i，道路的长度为L_i。两片草地之间，可能会有重复的道路连接它们。
牧场里有B头牛，第i头牛在草地P_i上。约翰在1号草地上派发巧克力，所以牛们要走到1号草地去拿到巧克力。所有的草地都是相互连通的。请帮助这些牛算一下，他们行走的最短距离分别是多少。

第一行：三个用空格分开的整数：N，M和B，1≤N≤100，1≤M≤500，1≤B≤100。
第二行到M+1行：在第i+1行有三个用空格分开的整数，代表第i条道路的信息：R_i，S_i和L_i，1≤R_i,S_i≤N，1≤L_i≤2000。
第M+2行到M+B+1行：在第i+M+1行有两个用空格分开的整数：P_i和Q_i，1≤P_i,Q_i≤N。

第一行到第B行：在第i行有一个整数，表示第i头牛行走的最短距离。

6 7 3
1 2 3
5 4 3
3 1 1
6 1 9
3 4 2
1 4 4
3 2 2
2
5
4

3
6
3