import java.text.spi.BreakIteratorProvider;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Vector;

class Edge {

  int from;
  int to;
  double originalCapacity;
  double capacity;
  double flow;
  Edge twin;

  public Edge(int f, int t, double c) {
    from = f;
    to = t;
    capacity = c;
    originalCapacity = c;
    flow = 0;
    twin = null;
  }

  public String toString() {
    return "(" + from + ", " + to + ")";
  }
}

public class FlowNetwork {

  int n, m;

  int s, t;

  Vector<Vector<Edge>> outEdges;
  Vector<Vector<Edge>> inEdges;
  Hashtable<String, Integer> nameToVertex;
  Vector<String> vertexNames;

  public String edgeToString(Edge e) {
    if (e == null) return "null";
    String from = vertexNames.get(e.from);
    String to = vertexNames.get(e.to);
    return "(" + from + ", " + to + ")";
  }

  public void depthFirstSearch(int u, Vector<Edge> predecessorEdge) {
    for (Edge e : outEdges.get(u)) {
      int v = e.to;
      if (e.capacity == 0 || predecessorEdge.get(v) != null) continue; // don't follow zero-cap edges

      predecessorEdge.set(v, e);
      depthFirstSearch(v, predecessorEdge);
    }
  }

  /*
   * returns a vector result of edges with result[v] = (u,v) and on a shortest path from s to v
   */
  public Vector<Edge> breadthFirstSearch(int startVertex) {
    Vector<Edge> predecessorEdge = new Vector<Edge>();
    for (int i = 0; i < n; i++) {
      predecessorEdge.add(null);
    }
    Queue<Integer> queue = new LinkedList<Integer>();
    queue.add(startVertex);
    predecessorEdge.set(startVertex, new Edge(startVertex, startVertex, 1)); // for dummy purposes
    while (queue.size() > 0) {
      int u = queue.remove();
      for (Edge e : outEdges.get(u)) {
        int v = e.to;
        if (e.capacity == 0 || predecessorEdge.get(v) != null) continue;
        predecessorEdge.set(v, e);
        queue.add(v);
      }
    }
    return predecessorEdge;
  }

  public FlowNetwork(int n) {
    this.n = n;
    nameToVertex = new Hashtable();
    vertexNames = new Vector(n);
    outEdges = new Vector<Vector<Edge>>();
    inEdges = new Vector<Vector<Edge>>();
    for (int i = 0; i < n; i++) {
      outEdges.add(new Vector<Edge>());
      inEdges.add(new Vector<Edge>());
    }
  }

  public void addVertex(String name) {
    int u = vertexNames.size();
    vertexNames.add(name);
    nameToVertex.put(name, u);
  }

  public void addEdge(String uName, String vName, double capacity) {
    if (!nameToVertex.containsKey(uName)) {
      String msg = "vertex " + uName + " not in hashtable";
      throw new RuntimeException(msg);
    }
    if (!nameToVertex.containsKey(vName)) {
      String msg = "vertex " + vName + " not in hashtable";
      throw new RuntimeException(msg);
    }
    int u = nameToVertex.get(uName);
    int v = nameToVertex.get(vName);
    Edge uv = new Edge(u, v, capacity);
    Edge vu = new Edge(v, u, 0);
    uv.twin = vu;
    vu.twin = uv;
    outEdges.get(u).add(uv);
    outEdges.get(v).add(vu);
    inEdges.get(u).add(vu);
    inEdges.get(v).add(uv);
  }

  public static FlowNetwork read(Scanner scanner) {
    // Log.print("number of vertices: ");
    int n = scanner.nextInt();
    // Log.print("number of edges: ");
    int m = scanner.nextInt();

    FlowNetwork graph = new FlowNetwork(n);

    for (int i = 0; i < n; i++) {
      // Log.print("name of vertex " + i + ": ");
      String name = scanner.next();
      // Log.println("I read vertex \"" + name + "\"");
      graph.addVertex(name);
    }

    for (int i = 0; i < m; i++) {
      // Log.print("enter edge " + (i + 1) + " out of " + m + ": ");
      String uName = scanner.next();
      String vName = scanner.next();
      Double capacity = scanner.nextDouble();
      /* 
      Log.println(
        "I read edge (" + uName + ", " + vName + ") with capacity " + capacity
      );
      */
      graph.addEdge(uName, vName, capacity);
    }

    String s = scanner.next();
    String t = scanner.next();

    graph.s = graph.nameToVertex.get(s);
    graph.t = graph.nameToVertex.get(t);
    Log.println("s = " + graph.s + " and t = " + graph.t);
    return graph;
  }


  /*
   * Runs Edmonds-Karp on this network. 
   * Upon returning, the local variable this.flow will be the maximum s-t-flow.
   * 
   * return value: a vector of Boolean, indicating for each vertex (indexed from 0 to n-1, not by vertex names)
   * whether it is reachable from s in the residual network.
   * 
   * Thus, the set of vertices for which the return value is true forms a minimum  s-t-cut.
   * 
   * It prints out a bunch of messagese. Set Log.silent to true to turn them off.
   */

  public Vector<Boolean> edmondsKarp() {
    Vector<Edge> predecessorEdge = breadthFirstSearch(s);
    int iterationNumber=0;
    while ((predecessorEdge = breadthFirstSearch(s)).get(t) != null) {
      iterationNumber++;
      // we have found a path from s to t;
      Double cmin = Double.POSITIVE_INFINITY;
      int currentVertex = t;

      while (currentVertex != s) {
        Edge currentEdge = predecessorEdge.get(currentVertex);
        cmin = Math.min(cmin, currentEdge.capacity);
        currentVertex = currentEdge.from;
      }

      /* now update flow and capacities */
      int v = t;
      int pathLength = 0;
      while (v != s) {
        Edge uv = predecessorEdge.get(v);
        int u = uv.from;
        // this is an edge e = (u,v)
        Edge vu = uv.twin;

        uv.flow += cmin;
        uv.capacity -= cmin;
        vu.flow -= cmin;
        vu.capacity += cmin;

        v = u;
        pathLength++;
      }
      Log.println(
        "Iteration " +
        iterationNumber +
        ". Path of length " +
        pathLength +
        " and capacity " +
        cmin +
        " found."
      );
    }

    Vector<Boolean> reachable = new Vector<Boolean>();
    for (int u = 0; u < n; u++) {
      if (predecessorEdge.get(u) != null || u == s)  {
        // Log.print(vertexNames.get(u) + " ");
        reachable.add(true);
      }
      else {
        reachable.add(false);
      }
    }
    return reachable;
  }



  public static void main(String args[]) {
    FlowNetwork nw = read(new Scanner(System.in));
    Vector <Boolean> reachable = nw.edmondsKarp();

    double valueOfFlow = 0;
    for (Edge e : nw.outEdges.get(nw.s)) {
      valueOfFlow += e.flow;
    }
    Log.println("value of max flow: " + valueOfFlow);

    double capacityOfCut = 0;
    for (int u = 0; u < nw.n; u++) {
      if (! reachable.get(u)) continue;
      for (Edge e : nw.outEdges.get(u)) {
        int v = e.to;
        if (!reachable.get(v)) capacityOfCut += e.originalCapacity;
      }
    }
    Log.println("capacity of cut: " + capacityOfCut);
   
    Log.println("The following vertices are reachable from s: ");


    for (int u = 0; u < nw.n; u++ ) {
      if (reachable.get(u)) {
        Log.print(nw.vertexNames.get(u) + " ");
      }
    }

    Log.println("");
  }

}