Server hosting

The city has a special computer network that is used for the transmission of information by the military. In connection with frequent rocket attacks, the infrastructure of the country suffered significant damage. Along with this, there were problems with the functioning of the computer network within the city.

Information about the initial structure of the computer network and the time of information transfer between the relevant network nodes is known. It is known that if there is a connection between the nodes, then the information is reached by the most profitable (fast) route.

After the occurrence of network damage, the information transfer time between some nodes decreased.

Determine where you need to place the main server so that the time to transfer information from the server to the most distant (the one to which the information reaches the slowest) node of the network would be minimal.

Input

The first line contains two natural numbers: n (1 ≤ n ≤ 1000) - the number of network nodes and m - the number of communication channels between these nodes .

Each of the following m lines contains information about the number of milliseconds c[i] for information transfer from node a[i] to b[i] in the form of three numbers: a[i] , b[i] and c[i] (1 ≤ a[i], b[i] ≤ n, 1 ≤ i ≤ m).

The next line contains the number k (0 ≤ k ≤ m) - the number of communication channels in which the speed of information transmission has decreased.

Next, there are k lines, each of which contains information by how much the information transfer time between the corresponding pair of nodes has decreased in the form of three numbers: x[i], y[i] and z[i] (1 ≤ x[i], y[i] ≤ n, 1 ≤ i ≤ m), where x[i], y[i] are the numbers of network nodes, and z[i] shows how many milliseconds the information transfer time between nodes x[i] and y[i] has increased.

Output

Determine the network node where to place the main server, so that the time of information transfer from the server to the most distant (the one to which the information reaches the slowest) network node would be minimal. If the server can be placed in several nodes, then list the numbers of such nodes in ascending order.

Examples

Note

The server should be placed in point 1. Then the data transfer time to the most separated node 4 will be 25 milliseconds.