package archipelago; import java.util.*; public class Dijkstra { public static void main(String[] args) { new Dijkstra().run(new Scanner(System.in)); } public void run(Scanner sc) { while (solve(sc)); } public boolean solve(Scanner sc) { int n = sc.nextInt(); int m = sc.nextInt(); if(n + m == 0) return false; land = new ArrayList>(); sea = new ArrayList>(); for(int i = 0; i < n; i++) { land.add(new ArrayList()); sea.add(new ArrayList()); } for(int i = 0; i < m; i++) { int x = sc.nextInt() - 1; int y = sc.nextInt() - 1; int t = sc.nextInt(); if(sc.next().equals("S")) { sea.get(x).add(new Edge(x, y, t)); sea.get(y).add(new Edge(y, x, t)); } else { land.get(x).add(new Edge(x, y, t)); land.get(y).add(new Edge(y, x, t)); } } for(int i = 0; i < n; i++) { Collections.sort(sea.get(i)); Collections.sort(land.get(i)); } int r = sc.nextInt(); list = new int[r]; for (int i = 0; i < r; i++) { list[i] = sc.nextInt() - 1; } System.out.println(dijkstra()); return true; } static class Edge implements Comparable { int src, dest, cost; Edge(int src, int des, int cost) { this.src = src; this.dest = des; this.cost = cost; } public int compareTo(Edge e) { return cost - e.cost; } } static class Node implements Comparable { int cur, ship, mailIndex, cost; public Node(int cur, int ship, int mailIndex, int cost) { this.cur = cur; this.ship = ship; this.mailIndex = mailIndex; this.cost = cost; } public int compareTo(Node o) { return cost - o.cost; } } private List> land; private List> sea; private int[] list; private static int BIG = 1 << 29; private int dijkstra() { int n = land.size(); int r = list.length; Queue queue = new PriorityQueue(); int[][][] costs = new int[n][n][r]; boolean[][][] check = new boolean[n][n][r]; for(int[][] tmp : costs) for(int[] tmp2 : tmp) Arrays.fill(tmp2, BIG); costs[list[0]][list[0]][0] = 0; queue.add(new Node(list[0], list[0], 0, 0)); while (!queue.isEmpty()) { Node node = queue.poll(); if (check[node.cur][node.ship][node.mailIndex]) continue; if(node.mailIndex == r - 1 && node.cur == list[node.mailIndex]) { return node.cost; } check[node.cur][node.ship][node.mailIndex] = true; for (Edge next : land.get(node.cur)) { int nextMailIndex = node.mailIndex + (node.cur == list[node.mailIndex] ? 1 : 0); int cost = node.cost + next.cost; if (check[next.dest][node.ship][nextMailIndex] || costs[next.dest][node.ship][nextMailIndex] <= cost) continue; costs[next.dest][node.ship][nextMailIndex] = cost; queue.add(new Node(next.dest, node.ship, nextMailIndex, cost)); } if(node.cur == node.ship) { for (Edge next : sea.get(node.cur)) { int nextMailIndex = node.mailIndex + (node.cur == list[node.mailIndex] ? 1 : 0); int cost = node.cost + next.cost; if (check[next.dest][next.dest][nextMailIndex] || costs[next.dest][next.dest][nextMailIndex] <= cost) continue; costs[next.dest][next.dest][nextMailIndex] = cost; queue.add(new Node(next.dest, next.dest, nextMailIndex, cost)); } } } return BIG; } }