Sum of City Distances in A Country

In country A, there are \(2^n - 1\) cities numbered from 1 to \(2^n - 1\), where city 1 is the capital. For every non‐capital city \(i\), there is a unidirectional first‐type road from city \(i\) to its parent city \(\lfloor \frac{i}{2} \rfloor\) with an associated length. In addition, there are \(m\) unidirectional second‐type roads. The \(j\)th second‐type road goes from city \(u_j\) to city \(v_j\) with a given length and satisfies the property that if one starts from \(v_j\) and repeatedly moves to the parent via the first‐type road, one will eventually reach \(u_j\).

For any two cities \(x\) and \(y\), define \(dist(x,y)\) as the minimum total length required to travel from \(x\) to \(y\) along the directed roads. If city \(y\) is unreachable from \(x\), we define \(dist(x,y)=0\). Also, \(dist(x,x)=0\) for every city \(x\).

Your task is to compute the sum

[ S = \sum_{x=1}^{2^n-1} \sum_{y=1}^{2^n-1} dist(x,y) ]

and output its value.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the parameter for the number of cities and the number of second‐type roads, respectively.

The second line contains \(2^n - 2\) integers. The \(i\)th integer (for \(i\) from 2 to \(2^n-1\)) is the length of the first-type road from city \(i\) to city \(\lfloor i/2 \rfloor\>.

Then follow \(m\) lines, each containing three integers \(u\), \(v\), and \(w\). Each such line represents a second‐type road from city \(u\) to city \(v\) with length \(w\). It is guaranteed that for each second‐type road, if one starts from \(v\) and follows the first‐type roads repeatedly, they will eventually reach \(u\).

outputFormat

Output a single integer which is the sum \(S=\sum_{x=1}^{2^n-1}{\sum_{y=1}^{2^n-1}{dist(x,y)}}\) as described above.

sample

2 1
1 2
1 3 1

6