import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Proyecto {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String texto = null;
		int n = 0, t = 0;
		Tarea tareas[] = null, inicio = null, fin = null;

		try {
			BufferedReader in = new BufferedReader(new InputStreamReader(
					System.in));
			texto = in.readLine();
			n = Integer.parseInt(texto);

			tareas = new Tarea[n];
			inicio = new TareaInicio();
			fin = new TareaFinal();
			inicio.setNombre("Inicio");
			inicio.setTiempo(0);
			fin.setNombre("Fin");
			fin.setTiempo(0);

			for (int i = 0; i < n; i++) {
				texto = in.readLine();
				tareas[i] = new Tarea();
				StringTokenizer st = new StringTokenizer(texto, ",");
				String nombre, tipo, tiempo;
				nombre = st.nextToken();
				tipo = st.nextToken();
				tareas[i].setNombre(nombre);
				if (tipo.equals("F")) {
					tiempo = st.nextToken();
					tareas[i].setTiempo(Integer.parseInt(tiempo));
				} else if (tipo.equals("A") || tipo.equals("P")) {
					tareas[i].setTiempo(0);
				}
			}
			texto = in.readLine();
			t = Integer.parseInt(texto);
			for (int i = 0; i < t; i++) {
				String org, des;
				Tarea torg = null, tdes = null;
				texto = in.readLine();
				StringTokenizer st = new StringTokenizer(texto, ",");
				org = st.nextToken();
				des = st.nextToken();
				if (org.equals(inicio.getNombre())) {
					torg = inicio;
				} else {
					for (int j = 0; j < n; j++) {
						if (org.equals(tareas[j].getNombre())) {
							torg = tareas[j];
							break;
						}
					}
				}

				if (des.equals(fin.getNombre())) {
					tdes = fin;
				} else {
					for (int j = 0; j < n; j++) {
						if (des.equals(tareas[j].getNombre())) {
							tdes = tareas[j];
							break;
						}
					}
				}
				if (torg == null || tdes == null) {
									}
				torg.addConcecuente(tdes);
				tdes.addAntecedente(torg);
			}
		} catch (IOException e) {
			System.out.println("Error en entrada de datos");
		}
		fin.terminacionRapida();
		inicio.inicioTardio();
		System.out.print("Ruta Critica: Inicio, ");
		for (int i = 0; i < n; i++) {
			if (tareas[i].isCritico()) {
				System.out.print(tareas[i].getNombre() + ", ");
			}
		}
		System.out.print(" Fin\n");
		System.out.println("Tiempo: " + fin.inicioTardio());
		System.out.println(inicio.getNombre() + " holgura: "
				+ inicio.getHolgura());
		for (int i = 0; i < n; i++) {
			System.out.println(tareas[i].getNombre() + " holgura: "
					+ tareas[i].getHolgura());
		}
		System.out.println(fin.getNombre() + " holgura: " + fin.getHolgura());

	}

}
////////////////////////

import java.util.ArrayList;

public class Tarea {
	private String nombre;
	private int tiempo;
	private int holgura;
	private ArrayList antecedentes;
	private ArrayList consecuentes;
	
	private int iniciomasrapido;
	private int terminacionmasrapida;
	private int iniciomastarde;
	private int terminaciontarde;

	Tarea(){
		this.antecedentes = new ArrayList();
		this.consecuentes = new ArrayList();
	}
	
	void setNombre(String nombre){
		this.nombre=nombre;
	}
	
	void setTiempo(int tiempo){
		this.tiempo=tiempo;		
	}

	public String getNombre() {
		return nombre;
	}

	public int getTiempo() {
		return tiempo;
	}
	
	public int terminacionRapida(){
		this.iniciomasrapido=0;
		for (int i = 0; i < antecedentes.size(); i++) {			
			if(((Tarea)antecedentes.get(i)).terminacionRapida()>this.iniciomasrapido){
				this.iniciomasrapido=((Tarea)antecedentes.get(i)).terminacionRapida();				
			}
		}
		this.terminacionmasrapida=this.iniciomasrapido+this.tiempo;
		return (this.terminacionmasrapida);
	}
	
	public int inicioTardio(){
		this.terminaciontarde=999999;
		for (int i = 0; i < consecuentes.size(); i++) {
			if(((Tarea)consecuentes.get(i)).inicioTardio()<this.terminaciontarde){
				this.terminaciontarde=((Tarea)consecuentes.get(i)).inicioTardio();				
			}
		}
		this.iniciomastarde=this.terminaciontarde-this.tiempo;
		return (this.iniciomastarde);
	}
	
	int getHolgura(){
		this.holgura=this.iniciomastarde-this.iniciomasrapido;
		return this.holgura;
	}	
	
	@SuppressWarnings("unchecked")
	public void addAntecedente(Tarea t){
		this.antecedentes.add(t);
	}
	
	@SuppressWarnings("unchecked")
	public void addConcecuente(Tarea t){
		this.consecuentes.add(t);		
	}
	
	boolean isCritico(){
		return (this.getHolgura()==0);		
	}
	
}

/////////////////////////


public class TareaFinal extends Tarea {
	

	public int inicioTardio(){
		return this.terminacionRapida();		
	}

	public int getHolgura(){
		return 0;		
	}
}

///////////////////


public class TareaInicio extends Tarea {
	


	public int terminacionRapida(){
		return 0;
	}
	
	public int getHolgura(){
		return 0;		
	}

}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public final class Grafo {

	private int nnodos;

	private int nodos[][][];

	private char nombres[];

	Grafo(int n) {
		this.nnodos = n;
		this.nodos = new int[nnodos][nnodos][2];
		this.nombres = new char[nnodos];
	}

	public void ingresarArco(int n1, int n2, int peso) {
		this.nodos[n1][n2][0] = peso;
		this.nodos[n2][n1][0] = peso;
		this.nodos[n1][n2][1] = n1;
		this.nodos[n2][n1][1] = n2;
	}

	public void ingresarNombre(int nodo, char letra) {
		this.nombres[nodo] = letra;
	}

	public void calcular() {
		int i, j, k;
		for (i = 0; i < this.nnodos; i++) {
			for (j = 0; j < this.nnodos; j++) {
				for (k = 0; k < this.nnodos; k++) {
					if (this.nodos[i][k][0] + this.nodos[k][j][0] < this.nodos[i][j][0]) {
						this.nodos[i][j][0] = this.nodos[i][k][0]
								+ this.nodos[k][j][0];
						this.nodos[i][j][1] = k;
					}
				}
			}
		}
	}

	public int pesominimo(int org, int des) {
		return this.nodos[org][des][0];
	}

	public String caminocorto(int org, int des) {
		String cam;
		if (org == des) {
			cam = "->" + nombres[org];
		} else {
			cam = caminocorto(org, this.nodos[org][des][1]) + "->"
					+ nombres[des];
		}
		return cam;
	}

	public char getNombre(int nodo) {
		return this.nombres[nodo];
	}

	public static void main(String args[]) throws IOException {
		Grafo g;

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String temp;
		int res;

		System.out.println("Entre el numero de nodos del grafo:\n");
		temp = br.readLine();
		res = Integer.parseInt(temp);

		g = new Grafo(res);

		for (int i = 0; i < res; i++) {
			System.out.println("Cual es el nombre del nodo [" + (i + 1)
					+ "]:\n");
			temp = br.readLine();
			g.ingresarNombre(i, temp.charAt(0));
		}
		for (int i = 0; i < res; i++) {
			for (int j = 0; j < res; j++) {
				if (i < j) {
					System.out.println("El nodo " + g.getNombre(i)
							+ " esta conectado con el nodo " + g.getNombre(j)
							+ " (s/n)\n");
					temp = br.readLine();
					if (temp.charAt(0) == 's') {
						int peso;
						System.out.println("Cual es el peso del arco:\n");
						temp = br.readLine();
						peso = Integer.parseInt(temp);
						g.ingresarArco(i, j, peso);
					} else {
						g.ingresarArco(i, j, 10000);
					}
				}
			}
		}

		g.calcular();
		for (int i = 0; i < res; i++) {
			for (int j = 0; j < res; j++) {
				if (i > j) {
					System.out.println("El camino mas corto entre los nodos:"
							+ g.getNombre(i) + "-" + g.getNombre(j) + " es: \n"
							+ g.caminocorto(i, j) + " y su peso es: "
							+ g.pesominimo(i, j));
				}
			}
		}
	}
}