Gradovi

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Graph<E> {

	int num_nodes;
	GraphNode<E> adjList[];

	@SuppressWarnings("unchecked")
	public Graph(int num_nodes, E[] list) {
		this.num_nodes = num_nodes;
		adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
		for (int i = 0; i < num_nodes; i++)
			adjList[i] = new GraphNode<E>(i, list[i]);
	}

	@SuppressWarnings("unchecked")
	public Graph(int num_nodes) {
		this.num_nodes = num_nodes;
        adjList = (GraphNode<E>[]) new GraphNode[num_nodes];
        for (int i = 0; i < num_nodes; i++)
                adjList[i] = new GraphNode<E>(i, null);
	}

	int adjacent(int x, int y) {
		// proveruva dali ima vrska od jazelot so
		// indeks x do jazelot so indeks y
		return (adjList[x].containsNeighbor(adjList[y])) ? 1 : 0;
	}

	void addEdge(int x, int y, float tezina) {
		// dodava vrska od jazelot so indeks x do jazelot so indeks y so
		// tezina
		if (adjList[x].containsNeighbor(adjList[y])) {
			adjList[x].updateNeighborWeight(adjList[y], tezina);
		} else
			adjList[x].addNeighbor(adjList[y], tezina);
	}

	void deleteEdge(int x, int y) {
		adjList[x].removeNeighbor(adjList[y]);
	}

/*	void dfsSearch(int node) {
		boolean visited[] = new boolean[num_nodes];
		for (int i = 0; i < num_nodes; i++)
			visited[i] = false;
		dfsRecursive(node, visited);
	}

	/*void dfsRecursive(int node, boolean visited[]) {
		visited[node] = true;
		System.out.println(node + ": " + adjList[node].getInfo());

		for (int i = 0; i < adjList[node].getNeighbors().size(); i++) {
			GraphNode<E> pom = adjList[node].getNeighbors().get(i);
			if (!visited[pom.getIndex()])
				dfsRecursive(pom.getIndex(), visited);
		}
	}

	/*void dfsNonrecursive(int node) {
		boolean visited[] = new boolean[num_nodes];
		for (int i = 0; i < num_nodes; i++)
			visited[i] = false;
		visited[node] = true;
		System.out.println(node+": " + adjList[node].getInfo());
		Stack<Integer> s = new Stack<Integer>();
		s.push(node);

		GraphNode<E> pom;

		while (!s.isEmpty()) {
			pom = adjList[s.peek()];
			GraphNode<E> tmp=null;
			for (int i = 0; i < pom.getNeighbors().size(); i++) {
				tmp = pom.getNeighbors().get(i);
				if (!visited[tmp.getIndex()])
					break;
			}
			if(tmp!=null && !visited[tmp.getIndex()]){
				visited[tmp.getIndex()] = true;
				System.out.println(tmp.getIndex() + ": " + tmp.getInfo());
				s.push(tmp.getIndex());
			}
			else
				s.pop();
		}

	}

/*	void bfs(int node){
		boolean visited[] = new boolean[num_nodes];
		for (int i = 0; i < num_nodes; i++)
			visited[i] = false;
		visited[node] = true;
		System.out.println(node+": " + adjList[node].getInfo());
		Queue<Integer> q = new LinkedQueue<Integer>();
		q.enqueue(node);

		GraphNode<E> pom;

		while(!q.isEmpty()){
			pom = adjList[q.dequeue()];
			GraphNode<E> tmp=null;
			for (int i = 0; i < pom.getNeighbors().size(); i++) {
				tmp = pom.getNeighbors().get(i);
				if (!visited[tmp.getIndex()]){
					visited[tmp.getIndex()] = true;
					System.out.println(tmp.getIndex()+": " + tmp.getInfo());
					q.enqueue(tmp.getIndex());
				}
			}


		}

	}
	float dijkstra(int from ,int to) {
		/* Minimalna cena do sekoe od teminjata */
		float distance[] = new float[this.num_nodes];
		int ofrom = from;
		/* dali za temeto e najdena konecnata (minimalna) cena */
		boolean finalno[] = new boolean[this.num_nodes];
		int pred[] = new int[this.num_nodes];

		for (int i = 0; i < this.num_nodes; i++) {
			distance[i] = -1;
			finalno[i] = false;
			pred[i] = i;
		}
		finalno[from] = true;
		distance[from] = 0;
		// vo sekoj cekor za edno teme se dobiva konecna minimalna cena
		while(from != to) {
			/*
			 * za site sledbenici na from presmetaj ja cenata (ako ne e konecna)
			 */
			Iterator<GraphNodeNeighbor<E>> it = adjList[from].getNeighbors().iterator();
			while (it.hasNext()) {
				GraphNodeNeighbor<E> pom = it.next();
				/* ako grankata kon sosedot nema konecna cena */
				if (!finalno[pom.node.getIndex()]) {
					/* ako ne e presmetana cena za temeto */
					if (distance[pom.node.getIndex()] < 0) {
						distance[pom.node.getIndex()] = distance[from] + pom.weight;
						pred[pom.node.getIndex()] = from;
					}
					/* inaku, ako e pronajdena poniska */
					else if (distance[from] + pom.weight < distance[pom.node.getIndex()]) {
						distance[pom.node.getIndex()] = distance[from] + pom.weight;
						pred[pom.node.getIndex()] = from;
					}
				}
			}
			/* najdi teme so min. cena koja ne e konecna */
			boolean minit = false; /* min. ne e inicijaliziran */
			int k = -1;
			float minc = 99999;
			/* proveri gi site jazli */
			for (int j = 0; j < this.num_nodes; j++) {
				if (!finalno[j] && distance[j] != -1) {
					/* ako cenata ne e konecna */
					if (minc > distance[j])
					{
						k = j;
						minc = distance[j];

					}
				}
			}
			finalno[from = k] = true;
		}
		Stack<Integer> stack = new Stack();
		int i = to;

		while(i != ofrom)
		{
			stack.push(i);
			i = pred[i];
		}
		stack.push(ofrom);

		while(!stack.isEmpty())
			System.out.print(adjList[stack.pop()].getInfo() + " ");
		System.out.println("");
		return distance[to];
	}



	@Override
	public String toString() {
		String ret = new String();
		for (int i = 0; i < this.num_nodes; i++)
			ret += i + ": " + adjList[i] + "\n";
		return ret;
	}

	/*public void setInfo(int k, E string) {
		adjList[k].setInfo(string);
	}*/
	public int getIndex(E inf)
	{
		for(int i=0; i<num_nodes; i++)
		{
			if(adjList[i].getInfo().equals(inf))
				return i;
		}
		return -1;
	}

}

class GraphNodeNeighbor<E> {
	GraphNode<E> node;
	float weight;

	public GraphNodeNeighbor(GraphNode<E> node, float weight) {
		this.node = node;
		this.weight = weight;
	}
}

class GraphNode<E> {
	private int index;//index (reden broj) na temeto vo grafot
	private E info;
	private LinkedList<GraphNodeNeighbor<E>> neighbors;

	public GraphNode(int index, E info) {
		this.index = index;
		this.info = info;
		neighbors = new LinkedList<GraphNodeNeighbor<E>>();
	}

	boolean containsNeighbor(GraphNode<E> o){
		GraphNodeNeighbor<E> pom = new GraphNodeNeighbor<E>(o,0);
		return neighbors.contains(pom);
		}
		void addNeighbor(GraphNode<E> o, float weight){
		GraphNodeNeighbor<E> pom = new GraphNodeNeighbor<E>(o,weight);
		neighbors.add(pom);
		}


	void removeNeighbor(GraphNode<E> o) {
		GraphNodeNeighbor<E> pom = new GraphNodeNeighbor<E>(o, 0);
		if (neighbors.contains(pom))
			neighbors.remove(pom);
	}

	void updateNeighborWeight(GraphNode<E> o, float weight) {
		Iterator<GraphNodeNeighbor<E>> i = neighbors.iterator();
		while (i.hasNext()) {
			GraphNodeNeighbor<E> pom = i.next();
			if (pom.node.equals(o))
				pom.weight = weight;
		}
	}

	@Override
	public boolean equals(Object obj) {
		@SuppressWarnings("unchecked")
		GraphNode<E> pom = (GraphNode<E>)obj;
		return (pom.info.equals(this.info));
	}

	public int getIndex() {
		return index;
	}

	public void setIndex(int index) {
		this.index = index;
	}

	public E getInfo() {
		return info;
	}

	public void setInfo(E info) {
		this.info = info;
	}

	public LinkedList<GraphNodeNeighbor<E>> getNeighbors() {
		return neighbors;
	}

	public void setNeighbors(LinkedList<GraphNodeNeighbor<E>> neighbors) {
		this.neighbors = neighbors;
	}



}
public class Gradovi {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Graph<String> g = new Graph<String>(n);

        n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++){
            String line = br.readLine();
        	String temp[] = line.split(" ");
            int k = Integer.parseInt(temp[0]);
            int j = Integer.parseInt(temp[2]);
            System.out.println(temp[0]);
            g.adjList[k].setInfo(temp[1]);
            g.adjList[j].setInfo(temp[3]);
            g.addEdge(k, j, Float.parseFloat(temp[4]));
        }
        int from = g.getIndex(br.readLine()), to = g.getIndex(br.readLine());
        br.close();

        float min = g.dijkstra(from, to);
        float min2 = g.dijkstra(to, from);
        System.out.println(min + min2);
	}
}