Server hosting#11337
The city has a special computer network used by the military for transmitting information. Due to frequent rocket attacks, the country's infrastructure has suffered significant damage, including problems with the functioning of the computer network within the city.
Information about the initial structure of the computer network and the time it takes to transfer information between network nodes is known. If there is a connection between nodes, information is transmitted along the fastest possible route.
After the damage to the network, the information transfer time between some nodes increased.
Determine the placement of the main server so that the time required to transfer information from the server to the farthest (i.e., slowest to reach) node of the network is minimized.
The first line contains two natural numbers (1 \leq n \leq 1000) — the number of nodes in the network, and — the number of communication channels between nodes.
Each of the following lines contains three integers: a_i, b_i, and c_i (1 \leq a_i, b_i \leq n, 1 \leq i \leq m), indicating that the time to transfer information from node a_i to node b_i is c_i milliseconds.
The next line contains the integer (0 \leq k \leq m) — the number of communication channels for which the information transfer time has increased.
The next lines each contain three integers: x_i, y_i, and z_i (1 \leq x_i, y_i \leq n, 1 \leq i \leq k), indicating that the transfer time between nodes x_i and y_i has increased by z_i milliseconds.
Determine at which network node to place the main server so that the maximum transfer time from the server to any other node is minimized. If there are several such nodes, output their numbers in ascending order.
Example 1
The server should be placed at node . In this case, the data transfer time to the most remote node will be 25 milliseconds.