#include <iostream>#include <string.h>#include <stdio.h>#define MAX_N 30#define MAX_L 1000#define MAX_VAL 1000000using namespace std;//graphdouble graph[MAX_N + 1][MAX_N + 1];double D[2][MAX_N + 1][MAX_N + 1];double pre[2][MAX_N + 1][MAX_N + 1];//struct node1{int from;int to;double dist;int townNum;int townList[MAX_N + 1];int distToTown[MAX_N + 1];}signs[MAX_L + 1];struct node2{string name;}towns[MAX_N + 1];int nodeNum, roadNum, towNum, sigNum, resPos;void init(){int i, j;for(i = 1; i <= MAX_L; i++){signs[i].townNum = 0;signs[i].dist = 0;signs[i].from = signs[i].to = 0;if(i <= MAX_N){towns[i].name = " ";for(j = 1; j <= MAX_N; j++){graph[i][j] = D[0][i][j] = D[1][i][j] = MAX_VAL;pre[0][i][j] = pre[1][i][j] = 0;}}}}bool byPass(int from, int to, int mid){while(to != from && to != 0){if(to == mid)return true;to = pre[resPos][from][to];}return false;}void swap(int pos1, int pos2, int signPos){int tempPos = signs[signPos].townList[pos2];int tempDist = signs[signPos].distToTown[pos2];signs[signPos].townList[pos2] = signs[signPos].townList[pos1];signs[signPos].distToTown[pos2] = signs[signPos].distToTown[pos1];signs[signPos].townList[pos1] = tempPos;signs[signPos].distToTown[pos1] = tempDist;}int compare(int pos1, int pos2, int signPos){if(signs[signPos].distToTown[pos1] < signs[signPos].distToTown[pos2])return -1;else if(signs[signPos].distToTown[pos1] > signs[signPos].distToTown[pos2])return 1;else{string str1 = towns[signs[signPos].townList[pos1]].name;string str2 = towns[signs[signPos].townList[pos2]].name;if(str1 < str2)return -1;else if(str1 == str2)return 0;elsereturn 1;}}void fastSort(int start, int end, int signPos){if(start < end){int posS = start, posE = end + 1;int curPos = start;while(true){while(compare(curPos, ++posS, signPos) > 0 && posS < end);while(compare(curPos, --posE, signPos) < 0 && posE > start);if(posS < posE)swap(posS, posE, signPos);elsebreak;}swap(start, posE, signPos);fastSort(start, posE - 1, signPos);fastSort(posE + 1, end, signPos);}}int main(){int i, j, k, from, to;double dist;string name;init();cin>>nodeNum>>roadNum>>towNum;for(i = 1; i <= roadNum; i++){cin>>from>>to>>dist;from++, to++;graph[from][to] = D[0][from][to] = dist;graph[to][from] = D[0][to][from] =dist;pre[0][from][to] = from;pre[0][to][from] = to;}for(i = 1; i <= towNum; i++){cin>>from>>name;from++;towns[from].name = name;}cin>>sigNum;for(j = 1; j <= sigNum; j++){cin>>from>>to>>dist;from++, to++;signs[j].from = from;signs[j].to = to;signs[j].dist = dist;}//processfor(k = 1; k <= nodeNum; k++){for(i = 1; i <= nodeNum; i++){for(j = 1; j <= nodeNum; j++){if(i == j)continue;int lastPos = (k + 1) % 2;int curPos = k % 2;double curVal = D[lastPos][i][j];double nextVal = D[lastPos][i][k] + D[lastPos][k][j];if(curVal < nextVal){if(curVal >= MAX_VAL)continue;D[curPos][i][j] = curVal;pre[curPos][i][j] = pre[lastPos][i][j];}else{if(nextVal >= MAX_VAL)continue;D[curPos][i][j] = nextVal;pre[curPos][i][j] = pre[lastPos][k][j];}}}}resPos = nodeNum % 2;for(i = 1; i <= sigNum; i++){int from = signs[i].from;int to = signs[i].to;for(j = 1; j <= MAX_N; j++){if(towns[j].name == " ")continue;if(byPass(from , j, to)){int num = ++signs[i].townNum;signs[i].townList[num] = j;signs[i].distToTown[num] = double(D[resPos][from][j] - signs[i].dist) + 0.5;}}fastSort(1, signs[i].townNum, i);for(j = 1; j <= signs[i].townNum; j++)printf("%-20s%dn", towns[signs[i].townList[j]].name.c_str(), signs[i].distToTown[j]);printf("n");}return 0;}
