In the flourishing land of Unionville, many streams flow from the mountains to nourish the village below. At various points, a stream may diverge into two, or two streams may converge into one. This occurs at exactly ~N~ junction points numbered from ~1~ to ~N~. Connecting each of these junction points are ~M~ stream segments, the ~i^\text{th}~ of which directs ~f_i~% of the water in junction ~u_i~ into junction ~v_i~.

Recently, some of the junctions have become polluted! Water at every junction has a measurable pollution value, which begins at ~0~ at the source and increases by ~p_i~ upon reaching junction ~i~. When water from two streams mix at a converging junction, the pollution values from each stream are averaged, weighted proportionally based on the volume of water in each stream, before ~p_i~ is added to the pollution value.

Until the pollution is cleaned up, the village chief needs to decide the safest places to source water for agriculture. Please help him determine the average pollution value of the water at each junction.

Constraints

All water starts at a single diverging source junction, which can flow to every other junction.

It is impossible to start at a junction, travel any number of streams, and return to the same junction.

The volume of water at every junction is guaranteed to be greater than ~10^{-16}~.

~2 \le N \le 10^5~

~1 \le M \le 1.5N~

~1 \le u_i, v_i \le N~

~1 \le f_i \le 100~

~0 \le p_i \le 100~

Input Specification

The first line contains two integers, ~N~ and ~M~.

The ~i^\text{th}~ of the following ~M~ lines contain three integers, ~u_i~ and ~v_i~, and ~f_i~.

The next line contains ~N~ integers, ~p_1, p_2, \dots, p_N~.

Output Specification

Output ~N~ lines, the ~i^\text{th}~ line of which contains a real number denoting the average pollution value at the ~i^\text{th}~ junction. Your answer will be considered correct if it is within an absolute or relative error of ~10^{-9}~.

Sample Input

6 8
2 6 100
3 4 41
3 2 59
4 2 100
5 4 27
5 3 73
6 1 62
6 1 38
8 73 40 36 100 54

Sample Output

284.6948
222.6948
140
157.029334270156
100
276.6948

Explanation for Sample Output

The river system looks like this: