Portal Energy Redistribution

ENLIGHTENED Headquarters has N portals numbered from 1 to N. Portal i initially contains A[i] units of energy. There are M bidirectional links (denoted by LINK) between portals. Each link connects two distinct portals and enables direct energy transfer between them. However, any portal i may send out at most A[i] units of energy in total directly to the portals it is connected to.

The ENLIGHTENED Command requires that after the transfers, each portal i should have at least B[i] units of energy. Note that energy can only be transferred directly between portals that are connected by a link, meaning indirect relays (through intermediate portals) are not allowed.

Formally, let t_ij be the energy transferred from portal i to portal j along a direct link. The constraints for a valid transfer plan are:

• For each portal i, its final energy is given by \[ \text{Final Energy}_i = A[i] - \sum_{j:(i,j) \text{ is a link}} t_{ij} + \sum_{j:(j,i) \text{ is a link}} t_{ji} \ge B[i]. \]
• For each portal i, the total energy it sends cannot exceed its initial energy: \[ \sum_{j:(i,j) \text{ is a link}} t_{ij} \le A[i]. \]
• Energy transfers can only occur along an existing link.

If a valid energy transfer plan exists, output one possible plan. Otherwise, output -1 to indicate that the required energy levels cannot be achieved.

inputFormat

The first line contains two integers N and M separated by a space.

The second line contains N integers: A[1], A[2], ..., A[N] representing the initial energy of each portal.

The third line contains N integers: B[1], B[2], ..., B[N] representing the required minimum energy for each portal after transfers.

The following M lines each contain two integers u and v indicating that there is a direct link between portal u and portal v.

outputFormat

If a valid transfer plan exists, the output should start with an integer T representing the number of energy transfer operations. The next T lines each contain three integers u, v, and x meaning that portal u transfers x units of energy directly to portal v.

If no valid plan exists, output a single line containing -1.

sample

2 1
10 2
5 4
1 2

1
1 2 2