#include <iostream>#include<map>#include<stdio.h>#include<memory.h>#include<string>#include<vector>#define N 1111using namespace std;map<string, int> M;vector<int> V;const int Inf = 0x7ffffff;int m, p, k, i, l, t, j, L, cnt;char s[10100], ss[10100];int g[1111][1111], path[1111], d[N];int cas = 0;void Dijkstra(int n, int s, int path[]) {int i, q[N], best_i, u, j;int top = n;for (i = 0; i < n; ++i)d[i] = Inf, q[i] = i;d[s] = 0;path[s] = s;for (i = 0; i < n; ++i) {best_i = 0;for (j = 0; j < top; ++j)if (d[q[j]] < d[q[best_i]])best_i = j;u = q[best_i];q[best_i] = q[--top];for (j = 0; j < top; ++j) {if (d[q[j]] > g[u][q[j]] + d[u])d[q[j]] = g[u][q[j]] + d[u], path[q[j]] = u;}}}int main() {while (scanf("%d%d", &p, &m) != EOF) {if (!p && !m)break;M.clear();gets(s);bool flag = false;cnt = 0;for (i = 0; i <= 1100; i++)for (j = 0; j <= 1100; j++)if (i == j)g[i][j] = 0;elseg[i][j] = Inf;for (i = 1; i <= p; i++) {scanf("%d", &k);gets(s);L = strlen(s);V.clear();while (s[j] == ' ')j++;bool boo = true;for (j = 0; j < L && boo;) {memset(ss, 0, sizeof(ss));l = 0;t = j;while (s[t] == ' ')t++;for (; t < L && s[t] != ' '; t++) {ss[l++] = s[t];if (s[t] == ':') {boo = false;break;}}ss[l++] = ' ';while (s[t] == ' ')t++;for (; t < L && s[t] != ','; t++) {if (s[t] == ':') {boo = false;break;}ss[l++] = s[t];}if (strcmp(ss,"Kevin, Bacon")==0) flag=true;if (!M[ss]) {M[ss] = ++cnt;}V.push_back(M[ss]);j = t + 1;}for (j = 0; j < (int) V.size(); j++)for (t = 0; t < (int) V.size(); t++)g[V[j] - 1][V[t] - 1] = g[V[t] - 1][V[j] - 1] = min(g[V[j] - 1][V[t] - 1], k);}Dijkstra(cnt, M["Kevin, Bacon"] - 1, path);printf("Database %dn", ++cas);while (m--) {gets(s);if (flag==false) {printf("%s: infinityn", s);continue;}if (d[M[s] - 1] < Inf)printf("%s: %dn", s, d[M[s] - 1]);elseprintf("%s: infinityn", s);}printf("n");}return 0;}
