Photographic Tour

Input: Standard Input

Output: Standard Output

Bangladesh Photographic Society is planning to arrange a Photographic Competition in Bangladesh. The topic of this competition is “The Nature of Bangladesh”. But their idea is little bit unusual. For each photographer, the organizer will provide a set of tickets of different prices and in a particular order, to travel and take pictures from various locations around Bangladesh. Photographers can travel from one place to another if the price of the ticket is same as the traveling cost between these two places. All the invited photographers have to collect these tickets from Dhaka and will start their journey from there. The participants may choose any route to the final destination - Cox’s Bazar where the final event is to be held. To make this tour simple (or complicatedJ ) the organizing committee has set some rules for this tour. All competitors will receive same set of tickets from the organizer. During their tour the photographers must use all the tickets in the order as they are given. The photographers can also travel to any place more than once but they have to reach at Cox’s Bazar using the final ticket. Otherwise, they will be disqualified from the competition. Now the organizing committee wants to know the number of places (including Dhaka and Cox’s Bazar) it is possible for the participants to visit during their tour. So, as a programmer they want your help.

Dhaka

Somewhere in Bangladesh

Cox’s Bazar

Input

There will be a set of test cases. Each test case starts with 2 numbers: N, E where N (2 ≤ N ≤ 100) represents the number of places in Bangladesh, E represents the connecting roads among these places. After that there will be E lines, each containing 3 numbers (x, y, z) which means that the traveling cost from place x to place y and place y to place x is z (0 ≤ z ≤ 100000). The first number T (T≤ 100) of the next line represents the number of tickets that each photographer will get from the organizer. After that there will be T numbers which represents the price of the tickets that a competitor has to use sequentially during his tour. Input will be terminated when N=E=0 and should not be processed. (For the sake of simplicity, you can assume that Dhaka is denoted by place 0 and Cox’s Bazar is denoted by place N-1).

Output

For each test case, there will be one line of output which contains the serial of output followed by an integer which represents the number of places where it is possible for any competitor to reach between the path from Dhaka (place 0) to Cox’s Bazar (place N-1). If it is not possible to reach from Dhaka to Cox’s Bazar using these tickets, your output should be 0. Look at the output for sample input for details.

Sample Input Output for Sample Input

3 2

0 1 1

0 2 2

1 1 2

3 2

0 1 1

0 2 2

0 0

Tour 1: 3

Tour 2: 0

Problem setter: Syed Monowar Hossain, Special Thanks: Derek Kisman