Power Supply

A tree $T$ with $N$ vertices is a power delivery network. Each vertex of $T$ is either a supply vertex or a demand vertex, and it carries one positive integer: the supply of a supply vertex, or the demand of a demand vertex. Each demand vertex receives power from exactly one supply vertex along the edges of $T$, so power flows through the edges. Each edge carries a positive integer called its capacity.

Delete edges to partition $T$ into subtrees. Deleting no edge is allowed, so $T$ itself can be the partition. The partition must satisfy both conditions below.

1. Each subtree contains exactly one supply vertex, and that supply is no less than the sum of all demands in the subtree.
2. The power flowing through each edge is no more than the capacity of that edge.

Decide whether $T$ has such a partition.

Figure 1(a) shows an example of a tree $T$. Each supply vertex is drawn as a rectangle and each demand vertex as a circle, the supply or the demand is written inside the shape, and the capacity is attached to each edge. Figure 1(b) shows one partition that satisfies the conditions. The deleted edges are dashed, the border of each subtree is dotted, the number on an edge is the power flowing through that edge, and the arrow gives the direction of the flow.

Figure 1. An example of a partition.

The first line contains the number of vertices $N$ of the tree $T$ ($1 \le N \le 300000$). The vertices are numbered $1, 2, \ldots, N$.

The $i$-th of the next $N$ lines contains two integers $a$ and $b$ ($a$ is 0 or 1, $1 \le b \le 10^9$). If $a = 0$, vertex $i$ is a supply vertex with supply $b$. If $a = 1$, vertex $i$ is a demand vertex with demand $b$.

Each of the next $N - 1$ lines contains three integers $x$, $y$, and $z$ ($1 \le x, y \le N$, $1 \le z \le 10^9$), describing an edge that joins vertex $x$ and vertex $y$ and has capacity $z$.

Print 1 on one line if $T$ has a partition that satisfies the conditions, and 0 otherwise.