Description:

Night Fury is a very rare and most dangerous and intelligent dragon from "master of dragon training 2". It is very different from other dragons in shape. It is similar to bats. At the same time, it combines the size of cats and the sharp eyes of wild wolves, with black scales on its body. The volume is petite, the expression and action are smart and lovely, and the ratio of wings is the largest in the dragon. There are up to three pairs of wings, so the flight time is longer, the speed is faster and more flexible. Different from the flame erupted by other dragons, it is a blue ball accompanied by calcium carbide gas and oxygen. It explodes after impact or flying for a certain distance. It has accurate attack, superb fighting skills, high intelligence, small size and superior flight and attack ability.

Now, as a young and brave Viking warrior, burp burp, you have a night evil named toothless boy. In order to change dreg's concept of killing dragons, you are on the way to catch up with the power hungry dreg. The cunning dreg hides in an unknown place, but you are smart. You can get the distance between some places by using the map in your hand, and you can also know the place where dreg hides from his population.

Now that the flight path of toothless boy is known, the villagers of bock island are very eager to know the total distance you and toothless boy have traveled in the course of Adventure (the same route does not need to be calculated repeatedly, but it may be repeated). If you encounter dreg on the flight path, you will immediately go to meet dreg and the flight is over.

Input:

There are multiple sets of data tests, which end with input 00.

For each group of input data, first enter nt, indicating that there are n locations (n < 2000). Then there are t lines to input. Input abvalue in each line indicates the length between a point and b point value. There is no road in the place that does not indicate the relationship. If the length of the second input of the same section of road is shorter than the previous one, the distance between a and b points is the shorter one. Then enter we, indicating that there are w lines of input and the e point where dreg is located. Entering cd in each line indicates that toothless boy flies from place c to place d, which must be two adjacent points. The sequence relationship indicates the places where toothless boy passes successively, so as to ensure that he will not pass through the non-existent road.

Output:

For each group of tests, output "Case#k:". First, K starts from 1.

Output the total journey of toothless boy in the process of adventure

Sample Input:

7 8
1 2 3
2 3 4
3 4 5
4 5 6
4 5 1
5 6 3
5 6 4
6 8 1
6 8
1 2
2 3
3 4
4 5
5 6
6 8
5 4
1 2 3
2 3 4
3 4 10
4 5 15
11 4
1 2
2 1
1 2
2 3
3 2
2 1
1 2
2 3
3 4
4 5
5 6
0 0

Sample Output:

Case #1: 17
Case #2: 17

#include "iostream"
#include "vector"

using namespace std;

/**
 * by kkmd66
 * @return
 */

int main() {
    int n, t, w, e;
    int count = 0;
    int sum = 0;

    while (cin >> n >> t && n != 0 && t != 0) {
        count++;

        //Fill map
        vector<vector<int>> map(t);
        for (int i = 0; i < t; ++i) {
            int a, b, value;
            cin >> a >> b >> value;

            map[i].push_back(a);
            map[i].push_back(b);
            map[i].push_back(value);
        }

        //Fill flight path
        cin >> w >> e;
        vector<vector<int>> step(w);
        for (int i = 0; i < w; ++i) {
            int c, d;
            cin >> c >> d;

            step[i].push_back(c);
            step[i].push_back(d);
        }

        //Eliminate repetitive flight paths
        for (int i = 0; i < step.size() - 1; ++i) {
            for (int j = i + 1; j < step.size(); ++j) {
                if ((step[i][0] == step[j][0] && step[i][1] == step[j][1]) ||
                    (step[i][0] == step[j][1] && step[i][1] == step[j][0])) {
                    step[j][0] = -1;
                    step[j][1] = -1;
                }
            }
        }

        //Adjustment chart
        for (int i = 0; i < map.size() - 1; ++i) {
            for (int j = i + 1; j < map.size(); ++j) {
                if ((map[i][0] == map[j][0] && map[i][1] == map[j][1]) ||
                    (map[i][0] == map[j][1] && map[i][1] == map[j][0])) {
                    map[i][2] = (map[i][2] < map[j][2] ? map[i][2] : map[j][2]);
                    map[j][0] = -1;
                    map[j][1] = -1;
                    map[j][2] = -1;
                }
            }
        }

        //Calculate total distance
        for (int i = 0; i < step.size(); ++i) {
            if (step[i][0] != -1) {
                if (step[i][1] == e) {
                    for (int j = 0; j < map.size(); ++j) {
                        if (map[j][1] == e){
                            sum+=map[j][2];
                        }
                    }
                    break;
                }
                else{
                    for (int j = 0; j < map.size(); ++j) {
                        if ((step[i][0] == map[j][0] && step[i][1] == map[j][1]) ||
                            (step[i][0] == map[j][1] && step[i][1] == map[j][0])) {
                            sum += map[j][2];
                        }
                    }
                }
            }
        }

        //output
        cout << "Case #" << count << ": " << sum << endl;

        //empty
        sum = 0;
    }
}