import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Navigation {
	static final int MAXNODE = 1000;
	
	static double fillD(
			Graph g, Map<String, Map<Set<Integer>, Double>> D, 
			String node, 
			Set<Integer> colors) {

		//System.out.println("X:" + node + " " + colors);

		// if it doesn't contain an entry for the node, create one.
		if(!D.containsKey(node)) {
			D.put(node, new HashMap<Set<Integer>, Double>());

			// if it contains an entry for the node, and 
			// also for the color set just return it
		} else if(D.get(node).containsKey(colors)) {
			return D.get(node).get(colors);
		}

		// we don't have an entry, so we must compute it:
		double mind = 1.0/0.0;
		// for all neighbors of valid colors
		colors.remove(g.color(node));
		for (String w : g.getNeighbors(node)) {
			if (colors.contains(g.color(w))) {

				// recursively compute the weights
				double q = fillD(g, D, w, colors) + g.weight(node, w);
				if( mind < 0 || mind > q) {
					mind = q;
				}
			}
		}
		colors.add(g.color(node));

		D.get(node).put(colors, mind);
		//System.out.println("X:" + node + " " + colors + " " + mind);
		return mind;
	}

	static void findPathWeight(String [][] entries, int numEntries, String u, String v) {
		Graph g = new Graph();
		g.readGraph(entries, numEntries);
		
		// create the set of all colors
		Set<Integer> allColors = new TreeSet<Integer>();
		for(String x : g.vertices()) {
			allColors.add(g.color(x));
		}

		// the dynamic programming array
		Map<String, Map<Set<Integer>, Double>> D = 
			new HashMap<String, Map<Set<Integer>, Double>>();

		// create the entry for u, the base case
		D.put(u, new HashMap<Set<Integer>, Double>());

		Set<Integer> S = null;
		for(int i : allColors) {
			S = new TreeSet<Integer>();
			S.add(i);
			D.get(u).put(S, (i==g.color(u))? 0.0: (1.0/0.0));
		}
		double length = fillD(g, D, v, allColors);

		// fill it
		System.out.println(u + " " + v + " " + ((length == 1.0 / 0.0)?"NONE":length));

	}

	static public void printEntries(String [][] entries, int numEntries) {
		for (int i = 0; i < numEntries; i++) {
			String node1 = entries[i][0];
			
			int nodeType = Integer.parseInt(entries[i][1]);
			System.out.print("Node " + node1 + " type = " + nodeType);
			
			if(entries[i][2] != null) {
				float wt = Float.parseFloat(entries[i][2]);
				System.out.print(" w/ edges of weight " + wt + " to neighbors =");

				int j = 3;
				while (entries[i][j] != null) {
					String node2 = entries[i][j];
					System.out.print(" " + node2);
					j++;
				}
			}
			System.out.println();
		}
	}
	
	static public void main(String [] args) {

		// read the graph
		Scanner inp = new Scanner(System.in);

		try {
			String line = inp.nextLine();
			if (!line.equals("GRAPH BEGIN"))
				throw new Exception();
			while (inp.hasNext()) {
				if (!inp.hasNext()) throw new Exception();

				// found new graph
				String [][] entries = new String [MAXNODE][];
				int numEntries = 0;

				while (inp.hasNext()) {
					String ln = inp.nextLine();
					if (ln.equals("GRAPH END")) 	//* end of graph specification
						break;

					String [] entry = new String[MAXNODE];
					int idx = 0;
					
					// read in entry (on single line)
					Scanner sc = new Scanner(ln);
					if(!sc.hasNext()) throw new Exception();
					entry[idx++] = sc.next();		// node
					
					if(!sc.hasNext()) throw new Exception();
					entry[idx++] = sc.next();		// node type

					if(sc.hasNext()) {
						entry[idx++] = sc.next();	// weight of edges to

						while (sc.hasNext()) {
							entry[idx++] = sc.next();	// these neighbors
						}
					} 
					entry[idx] = null;
					entries[numEntries++] = entry;	// save entry 
				}

				// printEntries(entries, numEntries);
				
				// process lines after graph, if any
				while (inp.hasNext()) {
					line = inp.nextLine();
					if (line.equals("GRAPH BEGIN")) {
						break;
					}
					Scanner s = new Scanner(line);
					String u = s.next(); // start node
					String v = s.next(); // end node
					findPathWeight(entries, numEntries, u, v);
				}
			}
		} catch(Exception e) {
			System.out.println("BAD INPUT FORMAT");
		}
	}

}