public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		String[] firstLine = cin.nextLine().split("\\s+");
		int n = Integer.parseInt(firstLine[0]);
		int k = Integer.parseInt(firstLine[1]);
		String s = firstLine[2];
		int[] hs = new int[n];
		Map<String, City> map = new HashMap<String, City>();
		City[] array = new City[n];
		hs[0] = 0;
		City scity = new City(s, 0);
		map.put(s, scity);
		array[0] = scity;
		for (int i = 1; i < n; i++) {
			String[] line = cin.nextLine().split("\\s+");
			String y = line[0];
			int h = Integer.parseInt(line[1]);
			hs[i] = h;
			City city = new City(y, i);
			map.put(y, city);
			array[i] = city;
		}

		int[][] matrix = new int[n][n];

		for (int i = 0; i < k; i++) {
			String[] line = cin.nextLine().split("\\s+");
			String x = line[0];
			String y = line[1];
			int cost = Integer.parseInt(line[2]);
			int a = map.get(x).index;
			int b = map.get(y).index;
			matrix[a][b] = cost;
			matrix[b][a] = cost;
		}

		PriorityQueue<City> que = new PriorityQueue<City>();
		que.offer(array[0]);
		array[0].setD(0);
		array[0].setChecked(true);
		int target = map.get("ROM").index;
		while (!que.isEmpty()) {
			City x = que.poll();
			if (x.index == target) {
				break;
			}

			for (int i = 0; i < n; i++) {
				if (x.index == i || array[i].isChecked()) {
					continue;
				}
				int a = matrix[x.index][i];
				if (a == 0) {
					continue;
				}
				City city = array[i];
				city.update(x, a);
				
			}
		}
	}