R. History

While local citizens are viewing an exhibition, they're very much interested in the background and history of the paintings. They often ask what a specific work is based on. The artists name other works that inspired them to paint that particular painting. The work that borrows from other great works a lot is considered to be great itself. Your goal is to create art that lasts, so you can't risk to base your paintings on questionable works. Given a set of credits (which pictures are borrowed from which), you need to find the greatness of each work.

The parameters required to calculate the greatness of a picture are carefully documented by art historians. According to the Academy of Numerical History of Art the greatness of a painting is strictly determined by the sum of two components: an intrinsic greatness (based on the size of the painting, the number of colors used and so on) and an inherited greatness: if P proportion of painting A is based on painting B then the greatness of A is increased by P times the greatness of B.

However if A and B are painted at the same time, they could be based on each other. This makes the calculations difficult, so the historians helpfully avoid mentioning such relations that may cause problems.

Input

First line of the input contains N, the number of paintings, and M, the number of relations between paintings. The second line contains the intrinsic greatness of each painting in order. Then M lines follow with A, B, P, saying that P proportion of painting A is borrowed from B. The paintings are numbered from 1.

Output

Output is the greatness of each painting on a single line in order. Each value must be precise to 3 digits after the decimal point.

Example input

3 2
0.5 1.0 2.0
1 2 .5
1 3 .2

Example output

1.4 1 2