#include<stdio.h>#include<iostream>#include<queue>#include<map>using namespace std;map<int,string>M;struct Node{int x;string name;friend bool operator<(Node a,Node b){if(a.x!=b.x) return a.x>b.x;else return a.name>b.name;}};priority_queue<Node>Q;map<int,string>::iterator it;const int INF = 1000000000;const int maxn = 31;void floyd(int n,int map[][maxn],int dist[][maxn],int pre[][maxn]){int i,j,k;for(i=0;i<n;i++){for(j=0;j<n;j++){dist[i][j]=map[i][j];pre[i][j]=i;}}for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)if(dist[i][k]!=INF&&dist[k][j]!=INF&&dist[i][j]>dist[i][k]+dist[k][j]){dist[i][j]=dist[i][k]+dist[k][j];pre[i][j]=pre[k][j];dist[j][i]=dist[j][k]+dist[k][i];pre[j][i]=pre[k][i];}}int main(){int n,m,k,s;int x,y;int t;Node p;double tmp;char name[20];int map[maxn][maxn];int dist[maxn][maxn];int pre[maxn][maxn];scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&k);for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(i==j) map[i][j]=0;else map[i][j]=INF;}while(m--){scanf("%d%d%lf",&x,&y,&tmp);map[x][y]=(int)(tmp*100+0.01);map[y][x]=(int)(tmp*100+0.01);}floyd(n,map,dist,pre);while(k--){scanf("%d %s",&x,name);M[x]=name;}scanf("%d",&s);while(s--){scanf("%d%d%lf",&x,&y,&tmp);for(int i=0;i<n;i++){if(dist[y][i]!=INF&&i!=x){if(dist[x][i]!=INF){if(dist[x][i]<dist[y][i]+dist[x][y]) continue;}it=M.find(i);if(it!=M.end()){p.x=(dist[y][i]+50+dist[x][y]-(int)(tmp*100+0.01))/100;p.name=it->second;Q.push(p);}}}while(!Q.empty()){Node front =Q.top();cout<<front.name;for(int j=0;j<20-front.name.length();j++)cout<<" ";cout<<front.x<<endl;Q.pop();}if(s) printf("n");}M.clear();if(t) printf("n");}return 0;}
