ANARC08F

2 1 4
A B
A <-5-> B
A <-4-> B
A <-3-> B
A <-2-> B
0 0 0
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
0 0 0
4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
0 0 0
4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
0 0 0
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
0 0 0
0 0 0
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
0 0 0
0 0 0
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
3 1 3
A C
A --3->               B
B --4->    C
C <-1-> B
0 0 0
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
3 1 3
A C
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
3 2 3
A C A
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
3 4 3
A C A B C
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
3 0 3
A 
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 0
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
3 0 3
A 
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 0
NewTroy Midvale Metrodale

3 0 3
A 
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
0 0 3
A 
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
1 0 0
A 
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
1 0 0
A 
0 0 0
import java.lang.*;
import java.io.*;
import java.util.Scanner;
class Vertex
{
	public String name = null;
	public int[] dest;
	public Vertex(int n)
	{
		dest = new int[n];
	}
}
class Graph 
{
	private Vertex vertex[];
	private int n;
	private int count = 0;
	private int min_distance(int dist[],boolean set[])
	{
		int i,min = 1001,min_index=-1;
		for(i=0;i= dist[i])
			{
				min = dist[i];
				min_index = i;
			}
		return min_index;
	}
	public Graph(int n)
	{
		this.n = n;
		vertex = new Vertex[this.n];
		for(int i=0;i0)
					dist[v]  =dist[u] + vertex[u].dest[v];
		}
		return dist;
	}
	public int shortdis(String src,int di)
	{
		int dist[] = new int[count],si = getindex(src);
		boolean set[] = new boolean[count];
		for(int i=0;i0)
					dist[v]  =dist[u] + vertex[u].dest[v];
		}
		return dist[di];
	}
	public int getindex(String src)
	{
		int i;
		for(i=0;i')
						dir = 0;
					else if(roads[k].charAt(0) == '<')
						dir = -1;
					else
						dir = 1;
					j++;
					while(roads[k].charAt(j) == '-')
						j++;
					while(roads[k].charAt(j) != '-')
					{
						wgt = wgt*10 + Integer.parseInt("" + roads[k].charAt(j));
						j++;
					}
					graph.insert(roads[0],roads[k+1],wgt,dir);
				}
				int dist[] = graph.shortdis(broken[0]),total = 0,si = graph.getindex(broken[0]);
				for(int i=1;i
1 0 0
A 
0 0 0
1 0 0
A 
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
import java.lang.*;
import java.io.*;
import java.util.Scanner;
class Vertex
{
	public String name = null;
	public int[] dest;
	public Vertex(int n)
	{
		dest = new int[n];
	}
}
class Graph 
{
	private Vertex vertex[];
	private int n;
	private int count = 0;
	private int min_distance(int dist[],boolean set[])
	{
		int i,min = 1001,min_index=-1;
		for(i=0;i= dist[i])
			{
				min = dist[i];
				min_index = i;
			}
		return min_index;
	}
	public Graph(int n)
	{
		this.n = n;
		vertex = new Vertex[this.n];
		for(int i=0;i0)
					dist[v]  =dist[u] + vertex[u].dest[v];
		}
		return dist;
	}
	public int shortdis(String src,int di)
	{
		int dist[] = new int[count],si = getindex(src);
		boolean set[] = new boolean[count];
		for(int i=0;i0)
					dist[v]  =dist[u] + vertex[u].dest[v];
		}
		return dist[di];
	}
	public int getindex(String src)
	{
		int i;
		for(i=0;i')
						dir = 0;
					else if(roads[k].charAt(0) == '<')
						dir = -1;
					else
						dir = 1;
					j++;
					while(roads[k].charAt(j) == '-')
						j++;
					while(roads[k].charAt(j) != '-')
					{
						wgt = wgt*10 + Integer.parseInt("" + roads[k].charAt(j));
						j++;
					}
					graph.insert(roads[0],roads[k+1],wgt,dir);
				}
				int dist[] = graph.shortdis(broken[0]),total = 0,si = graph.getindex(broken[0]);
				for(int i=1;i
#include 

using namespace std;

#define pb push_back
#define inf 26116
#define mp make_pair

typedef long long ll;
vector  > grafo[104];
vector  > grafo2[104];
int n;

int fun(string str){
    char j[10];
    int h=0,he;
    for(int i=1; i> he;
    return(he);
}

vector  dijkstra(int raiz){
    vector d(n+1,-1);
    vector marcas(n+1,false);
    priority_queue  > cola;
    d[raiz]=0;
    pair p=make_pair(0,raiz);
    cola.push(p);
    while(!cola.empty()){  //ESTE WHILE ITERA N VECES
        int u = cola.top().second; cola.pop();
        if(!marcas[u]){
            marcas[u] = true;
            for(int i=0; id[u]+valor){
                    d[v]=d[u]+valor;
                    if(!marcas[v])cola.push(make_pair(-d[v],v));
                }
            }
        }
    }
    return(d);
}


vector  dij1(int raiz){
    vector d(n+1,-1);
    vector marcas(n+1,false);
    priority_queue  > cola;
    d[raiz]=0;
    pair p=make_pair(0,raiz);
    cola.push(p);
    while(!cola.empty()){  //ESTE WHILE ITERA N VECES
        int u = cola.top().second; cola.pop();
        if(!marcas[u]){
            marcas[u] = true;
            for(int i=0; id[u]+valor){
                    d[v]=d[u]+valor;
                    if(!marcas[v])cola.push(make_pair(-d[v],v));
                }
            }
        }
    }
    return(d);
}

int main(){
	int a,b,c,caso=0;
	while(true){
		caso++;
		scanf("%d %d %d",&a,&b,&c);
		if(a==0 && b==0 && c==0) break;
		else{
			n=a;
			map  mapa; int num=1;
			vector  cui;
			for(int i=0; i<=b; i++){
				string p1;
				cin>>p1;
				if(!mapa[p1]){mapa[p1]=num; num++;}
				cui.pb(mapa[p1]);
			}
			for(int ir=0; ir>p11>>p12>>p13;
				if(mapa[p13]) p3=mapa[p13];
				if(mapa[p11]) p=mapa[p11];
				if(!mapa[p11]){
					mapa[p11]=num;
					p=num;
					num++;

				}
				if(!mapa[p13]){
					mapa[p13]=num;
					p3=num;
					num++;
				}
				int v=fun(p12);
				if(p12[0]=='<' && p12[p12.size()-1]=='>'){
					grafo[p].pb(mp(p3,v));
					grafo[p3].pb(mp(p,v));
					grafo2[p].pb(mp(p3,v));
					grafo2[p3].pb(mp(p,v));
				}else if(p12[0]=='<'){
					grafo[p3].pb(mp(p,v));
					grafo2[p].pb(mp(p3,v));
				}else{
					grafo[p].pb(mp(p3,v));
					grafo2[p3].pb(mp(p,v));

				}
			}
			ll suma=0;
			vector  dist,d2;
			int raiz=cui[0];
			dist=dijkstra(raiz);
			d2=dij1(raiz);
			for(int i=1; i
2 1 4
A B
A <-5-> B
A <-4-> B
A <-3-> B
A <-2-> B

4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
3 1 3
A C
A --3->               B
B --4->    C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
3 1 3
A C
A <-3-> B
B --4-> C
C <-1-> B

3 2 3
A C A
A <-3-> B
B --4-> C
C <-1-> B

3 4 3
A C A B C
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 0
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 0
NewTroy Midvale Metrodale

3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

0 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
0 0 0
2 1 4
A B
A <-2-> B
A <-4-> B
A <-3-> B
A <-5-> B

4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


3 1 3
A C
A --3->               B
B --4->    C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


3 1 3
A C
A <-3-> B
B --4-> C
C <-1-> B

3 2 3
A C A
A <-3-> B
B --4-> C
C <-1-> B

3 4 3
A C A B C
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline



3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 0
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline



3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B


6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 0
NewTroy Midvale Metrodale


3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

0 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
0 0 0
4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
2 1 4
A B
A <-2-> B
A <-4-> B
A <-3-> B
A <-5-> B

4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


3 1 3
A C
A --3->               B
B --4->    C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


3 1 3
A C
A <-3-> B
B --4-> C
C <-1-> B

3 2 3
A C A
A <-3-> B
B --4-> C
C <-1-> B

3 4 3
A C A B C
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline



3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 0
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline



3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B


6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 0
NewTroy Midvale Metrodale


3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

0 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
0 0 0
2 1 4
A B
A <-5-> B
A <-4-> B
A <-3-> B
A <-2-> B

4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
3 1 3
A C
A --3->               B
B --4->    C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
3 1 3
A C
A <-3-> B
B --4-> C
C <-1-> B

3 2 3
A C A
A <-3-> B
B --4-> C
C <-1-> B

3 4 3
A C A B C
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 0
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 0
NewTroy Midvale Metrodale

3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

0 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
0 0 0
3 4 3
A C A B C
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
#define _CRT_SECURE_NO_WARNINGS

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

typedef pair, int> relationType;
#define isLeftToRightDirected first.first
#define isRightToLeftDirected first.second
#define cost second
#define infinity INT_MAX / 2
const int maxLocationsN = 501;

int graph[maxLocationsN][maxLocationsN];

queue carsToPickup;
map locationId;

int locationsN, brokenCarsN, streetsN;
string garageLocationName;

void floyd_warshall()
{
	for (int k = 1; k <= locationsN; k++)
		for (int i = 1; i <= locationsN; i++)
			for (int j = 1; j <= locationsN; j++)
				graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
}

inline string nextString()
{
	char locationNameBuffer[12];
	scanf("%s", &locationNameBuffer);
	return locationNameBuffer;
}

inline int getLocationId_assignIfNeeded(string location)
{
	if (locationId.find(location) == locationId.end())
		locationId[location] = locationId.size() + 1;

	return locationId[location];
}

int getCost(string relationAsString)
{
	string costAsString;
	set delimiters;
	delimiters.insert('-');
	delimiters.insert('<');
	delimiters.insert('>');
	for (auto currentChar : relationAsString)
		if (delimiters.find(currentChar) == delimiters.end())
			costAsString += currentChar;
	return stoi(costAsString);
}

inline relationType parseRelation(string relationAsString)
{
	if(relationAsString[0] == '<' && relationAsString[relationAsString.size() - 1] == '>')
		return{ {false, false}, getCost(relationAsString) };
	if(relationAsString[0] == '<')
		return{ {false, true}, getCost(relationAsString) };
	if (relationAsString[relationAsString.size() - 1] == '>')
		return{ {true, false}, getCost(relationAsString) };
	return { { false, false }, -1 };
}

int solve()
{
	int garage = locationId[garageLocationName], sum = 0;
	while(!carsToPickup.empty())
	{
		auto next = carsToPickup.front();
		carsToPickup.pop();
		sum += graph[next][garage] + graph[garage][next];
	}
	return sum;
}

int main()
{
	scanf("%d %d %d", &locationsN, &brokenCarsN, &streetsN);
	int test = 0;
	while(!(locationsN == 0 && brokenCarsN==0 && streetsN == 0))
	{
		test++;
		for (int i = 1; i <= locationsN; i++)
			for (int j = 1; j <= locationsN; j++)
				graph[i][j] = i == j ? 0 : infinity;

		locationId.clear();
		carsToPickup = queue();
		garageLocationName = nextString();

		for(int c = 0; c < brokenCarsN; c++)
			carsToPickup.push(getLocationId_assignIfNeeded(nextString()));
		for(int s = 0; s < streetsN; s++)
		{
			auto lhsName = nextString();
			auto relationAsString = nextString();
			auto rhsName = nextString();
			auto relation = parseRelation(relationAsString);
			if (relation.isLeftToRightDirected)
				graph[getLocationId_assignIfNeeded(lhsName)][getLocationId_assignIfNeeded(rhsName)] = relation.cost;
			if (relation.isRightToLeftDirected)
				graph[getLocationId_assignIfNeeded(rhsName)][getLocationId_assignIfNeeded(lhsName)] = relation.cost;
			if(!relation.isLeftToRightDirected && !relation.isRightToLeftDirected)
			{
				graph[getLocationId_assignIfNeeded(lhsName)][getLocationId_assignIfNeeded(rhsName)] = relation.cost;
				graph[getLocationId_assignIfNeeded(rhsName)][getLocationId_assignIfNeeded(lhsName)] = relation.cost;
			}
		}
		floyd_warshall();
		printf("%d. %d\n", test, solve());
		scanf("%d %d %d", &locationsN, &brokenCarsN, &streetsN);
	}
	return 0;
}
0 0 3
A 
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
frghth2 1 4
A B
A <-5-> B
A <-4-> B
A <-3-> B
A <-2-> B
0 0 0
2 1 4
A B
A <-5-> B
A <-4-> B
A <-3-> B
A <-2-> B
0 0 0
3 4 3
A C A B C
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
0 0 0
0 0 0
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 0
NewTroy Midvale Metrodale

3 0 3
A 
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
3 0 3
A 
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
0 0 0
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
0 0 0
0 0 0
4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
2 1 4
A B
A <-2-> B
A <-4-> B
A <-3-> B
A <-5-> B
0 0 0
4 2 5
NewTroy Midvale Metrodale
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline

4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy --20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


3 1 3
A C
A --3->               B
B --4->    C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


3 1 3
A C
A <-3-> B
B --4-> C
C <-1-> B

3 2 3
A C A
A <-3-> B
B --4-> C
C <-1-> B

3 4 3
A C A B C
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline



3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 0
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline



3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B


6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 0
NewTroy Midvale Metrodale


3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

0 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
0 0 0
4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
2 1 4
A B
A <-2-> B
A <-4-> B
A <-3-> B
A <-5-> B
4 2 5
NewTroy Midvale Metrodale
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy --20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
0 0 0
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


3 1 3
A C
A --3->               B
B --4->    C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


3 1 3
A C
A <-3-> B
B --4-> C
C <-1-> B

3 2 3
A C A
A <-3-> B
B --4-> C
C <-1-> B

3 4 3
A C A B C
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline



3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 0
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline



3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B


6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 0
NewTroy Midvale Metrodale


3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

0 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
0 0 0
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
0 0 0
4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
2 1 4
A B
A <-2-> B
A <-4-> B
A <-3-> B
A <-5-> B
4 2 5
NewTroy Midvale Metrodale
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy --20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
0 0 0
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
0 0 0
3 2 3
A C A
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
3 1 3
A C
A --3->               B
B --4->    C
C <-1-> B
0 0 0 
2 1 4
A B
A <-5-> B
A <-4-> B
A <-3-> B
A <-2-> B
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
3 1 3
A C
A --3->               B
B --4->    C
C <-1-> B
0 0 0
1 0 0
A 
A <-3-> B
B --4-> C
C <-1-> B
0 0 0
#include 
using namespace std;
vector < pair > adj1[10008],adj2[10008];
priority_queue < pair , vector< pair >, greater < pair > > Q;
long long int dist[10008],dist1[10008],visit[10008];
long long int c,n;
void dijkstra(long long int src,long long int dest)
{
	long long int sz;
	long long int u,v,w,i;
	for(i=0;idist[u]+w && visit[v]==0) {
				dist[v]=dist[u]+w;
				Q.push(make_pair(dist[v],v));
			}
		}
		visit[u]=1;
	} 
 	for(i=0;idist1[u]+w && visit[v]==0) {
				dist1[v]=dist1[u]+w;
				Q.push(make_pair(dist1[v],v));
			}
		}
		visit[u]=1;
	}	
}	

int main()
{
	long long int t_no=1;
	map mp,mp1;
	string s,s1,s2;
	long long int u,v,w,cnt=0;
	char l1,l2,r1,r2;
	long long int i,r;
	scanf("%lld%lld%lld",&n,&c,&r);
	while(n!=0 && c!=0 && r!=0) {
		cin>>s;
		mp.insert(make_pair(s,cnt));
		cnt++;
		for(i=1;i<=c;i++) {
			cin>>s;
			if(mp.find(s)==mp.end()) {
				mp.insert(make_pair(s,cnt));
				cnt++;
				mp1.insert(make_pair(s,1));
			}
			else
				mp1[s]++;
		}
		for(i=0;i>s1>>l1>>l2>>w>>r2>>r1>>s2;
			if(mp.find(s1)==mp.end()) {
				mp.insert(make_pair(s1,cnt));
				cnt++;
			}
			if(mp.find(s2)==mp.end()) {
				mp.insert(make_pair(s2,cnt));
				cnt++;
			}
			if(r1=='>' && l1=='-') {
				adj1[mp[s1]].push_back(make_pair(w,mp[s2]));
				adj2[mp[s2]].push_back(make_pair(w,mp[s1]));
			}
			if(r1=='-' && l1=='<') {
				adj1[mp[s2]].push_back(make_pair(w,mp[s1]));
				adj2[mp[s1]].push_back(make_pair(w,mp[s2]));
			}
			if(l1=='<' && r1=='>') {
				adj1[mp[s1]].push_back(make_pair(w,mp[s2]));	
				adj1[mp[s2]].push_back(make_pair(w,mp[s1]));
				adj2[mp[s2]].push_back(make_pair(w,mp[s1]));	
				adj2[mp[s1]].push_back(make_pair(w,mp[s2]));
			}
		}
		map :: iterator it;
		dijkstra(0,0);
		long long int res=0,mul;
		for(it=mp1.begin();it!=mp1.end();it++) {
			i=mp[it->first];
			mul=it->second;
			res=res+(dist[i]+dist1[i])*mul;
		}
		printf("%lld. %lld\n",t_no,res);
		for(i=0;i
4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
2 1 4
A B
A <-2-> B
A <-4-> B
A <-3-> B
A <-5-> B

4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


3 1 3
A C
A --3->               B
B --4->    C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


3 1 3
A C
A <-3-> B
B --4-> C
C <-1-> B

3 2 3
A C A
A <-3-> B
B --4-> C
C <-1-> B

3 4 3
A C A B C
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline



3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 0
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline



3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B


6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 0
NewTroy Midvale Metrodale


3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

0 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
0 0 0
4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
2 1 4
A B
A <-2-> B
A <-4-> B
A <-3-> B
A <-5-> B
4 2 5
NewTroy Midvale Metrodale
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy --20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale <-5-> Bakerline
A --12-> B
B <-40-> Midvale
4 2 5
NewTroy Midvale Metrodale
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
0 0 0
6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


3 1 3
A C
A --3->               B
B --4->    C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


3 1 3
A C
A <-3-> B
B --4-> C
C <-1-> B

3 2 3
A C A
A <-3-> B
B --4-> C
C <-1-> B

3 4 3
A C A B C
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline



3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 0
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline



3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B


6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 0
NewTroy Midvale Metrodale


3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

0 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
0 0 0
2 1 4
A B
A <-2-> B
A <-4-> B
A <-3-> B
A <-5-> B

4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

4 3 5
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


3 1 3
A C
A --3->               B
B --4->    C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline


3 1 3
A C
A <-3-> B
B --4-> C
C <-1-> B

3 2 3
A C A
A <-3-> B
B --4-> C
C <-1-> B

3 4 3
A C A B C
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline



3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale


4 2 0
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --5-> Bakerline



3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B


6 3 7
NewTroy Midvale Metrodale Bakerline
NewTroy   --20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-5-> Bakerline
Metrodale <-30-> NewTroy
Metrodale  <-5-> Bakerline
A --12-> B
B <-40-> Midvale



4 2 0
NewTroy Midvale Metrodale


3 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

0 0 3
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
A <-3-> B
B --4-> C
C <-1-> B

1 0 0
A
0 0 0
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-50-- Bakerline
Metrodale <-350-> NewTroy
Metrodale  --8-> Bakerline
0 0 0
4 2 5
NewTroy Midvale Metrodale
NewTroy   <-20-> Midvale
Midvale   --50-> Bakerline
NewTroy    <-54-- Bakerline
Metrodale <-30-> NewTroy
Metrodale  --52-> Bakerline
0 0 0
2 1 4
A B
A <-5-> B
A <-4-> B
A <-3-> B
A <-20-> B
0 0 0