Problem H: Pricey Network

Pricey Network, PNet for short, is a virtual network built on top of the Internet protocol. In contrast to connection-oriented transmission of data (unicast) and the transmission from a sender to all destinations in a network (broadcast) it provides a facility to send data to all hosts that have joined a so-called communication group. All members of a group are able to send data to and receive data from the group.

Your program is to simulate a simplified version of the PNet. In this setting PNet is a combination of routers and hosts, each host directly connected to one of the routers. A router and all the hosts directly connected to it are called a sub-PNet. Routers are connected via T-links which are simple unidirectional communication channels: data packets sent from one side through a T-link are received on its other side.

In order to become a member of a communication group, a host must send a protocol message to its corresponding router specifying the identity of the group it wants to join. As a consequence the host will receive all data packets sent to this group as long as it is a member of the group.

In order to send a data packet to a communication group, a host sends the packet to the router within its sub-PNet. Every router duplicates all received packets and sends them through each of its outgoing T-links. After that, it sends copies of the packet to all hosts on its sub-PNet that have joined the group specified in the packet. For this problem we assume that all the transmissions are instantaneous.

The distribution of a packet within PNet is restricted through an integer value called Value Tag, VT for short, which is assigned to every packet. If a packet is sent through a T-link its VT is decremented by the cost of using the link (an integer value) specified for each T-link. A packet will not be sent over a T-link if its VT is lower than the cost of using the T-link. (Remark. The value tags of packets are then used by the accountants to establish the monthly payments by all hosts, but we are not concerned here with accounting.)


Your program should read input from file named network.dat. The input will consist of several PNet descriptions. The first part of each description defines the network topology, and the second part describes the activities on this network. The first part starts with a line containing a single integer m (1 ≤ m ≤ 10), the number of sub-PNets in the network. A value of m = 0 indicates the end of input. The following lines contain descriptions of m sub-PNets.

Each sub-PNet description starts with a line containing the name of the router (given as a string of at most 20 non-blank characters) followed by an integer for the number of remaining lines in the sub-PNet description. These lines can be of two kinds:

          H <Host address>
          T <Cost of using> <Destination sub-PNet>

The first type of a line identifies a host in the sub-PNet by giving its <Host address> which is an integer. The second type of line describes a T-link connecting this sub-PNet's router to a router at the other end of the link in another sub-PNet named <Destination sub-PNet>. The cost of using this T-link is given by <Cost of using> which is a positive integer.

The first line of the second part contains a single integer not bigger than 1000 indicating the number of lines in the following activity description. Each one of these lines describes the activity of a host: join a group (tag J), leave a group (tag L) or send a packet to a group (tag S).

J <Host Address> <Group Address>
L <Host Address> <Group Address>
S <Host Address> <Group Address> <Packet ID> <VT>

The <Group Address>, <Packet ID> and <VT> are positive integer values with obvious meaning. All names used for the routers and all host addresses used in a scenario, as well as all packet IDs are unique. VTs of packets will be at most 1000. There will be at most 50 hosts and 100 T-links in a network and at most 20 active groups (i.e, groups for which there is at least one member host) at any time. No host will try to leave a group that it is not in, nor try to join a group it is in.


Print, to the output, the packets received by hosts in the network for each scenario. If hosts receive multiple copies of a packet (routed via different paths), they keep only the copy with the highest VT (reaching them via the cheapest path). For each network description, first output the number of the network, as shown in the sample output. Each one of the subsequent lines is of the format

<Host Address> <Packet ID> <VT>

meaning that host <Host Address> received the packet identified by <Packet ID> with the remaining value tag <VT>. The three numbers in each line should be separated by a single space character. The output must be sorted in ascending order: first by the host address and second by the packet ID.

Output a blank line after each test case.

Sample input

Calgary 6
H 53127
T 3 Lethbridge
H 53128
H 53129
H 53230
T 7 Edmonton
Edmonton 5
T 16 Lethbridge
T 10 Calgary
H 22714
H 22715
H 22716
Lethbridge 3
H 1024
H 2048
T 7 Calgary
J 1024 72
J 22716 62
J 53129 62
J 1024 62
S 1024 62 901 117
J 53230 62
S 1024 62 230 192
J 53128 6
S 1024 62 231 192
L 53230 62
S 22716 62 902 73
S 53129 62 335 51
L 22716 62
L 1024 72
L 53129 62 

Output for sample input

Network #1
1024 230 192
1024 231 192
1024 335 48
1024 901 117
1024 902 60
22716 230 178
22716 231 178
22716 335 44
22716 901 103
22716 902 73
53129 230 185
53129 231 185
53129 335 51
53129 901 110
53129 902 63
53230 230 185
53230 231 185

PZER 97, adapted by P. Rudnicki