Card Purchase Reconstruction

After their pool burst, Mirko and Slavko started collecting cards. In their neighborhood, collecting cards is taken seriously, and buying or trading cards follows strict rules.

A purchase is always made by two children together. Each child pays half of the price, and two cards are bought. Then they race to the fountain downtown. The child who arrives first gets both cards. If they arrive at exactly the same time, each child gets one card.

At first the rules seemed fine, but later some children were suspected of having card counts that could not have been produced only by such purchases.

One day all the children met to check whether anything irregular had happened. They agreed on the exact number of cards each child currently has. They also reconstructed a partial list of pairs of children who went to the store together, but they do not know who won the races after those purchases.

Assume that before any purchase, no child had any cards. Construct a complete list of purchases and race outcomes so that, after all purchases, every child has exactly the given number of cards. The remembered purchases from the input must be included. If several answers are possible, output any one of them.

The first line contains two integers N and M (1 <= N <= 100, 0 <= M <= 1000): the number of children and the number of remembered purchases. The children are labeled from 1 to N.

The second line contains N integers, where the i-th integer is the number of cards child i currently has.

Each of the next M lines contains two integers: the labels of the two children who made that remembered purchase.

On the first line, output the total number of purchases.

Each following line must describe one purchase with three integers: the two children who made the purchase, followed by 0, 1, or 2, the number of cards received by the first child on that line. The second child receives the remaining cards from that purchase.

A valid solution always exists, although it may not be unique. The total number of purchases in a valid output is at most 1000.

In the first sample, only children 1 and 2 exist. Child 1 must finish with five cards and child 2 with one card. One possible construction is to split the first purchase evenly, then let child 1 take both cards in the next two purchases.