Minimalist Security Act

A map of Mafiatown's road network is given. The network consists of intersections and bidirectional streets connecting them. The streets cross only at the intersections but may pass through tunnels or flyovers. Each intersection v has a police station manned by p(v) policemen. A street linking intersections u and v is considered safe if the total number of policemen at its two ends is at least b(u,v). Initially, for every street, we have

$$ p(u)+p(v)\ge b(u,v) $$

Due to a crisis, the mayor enacts the Minimalist Security Act (MSA): from each station a certain number (possibly zero) of policemen is laid off. Denote by z(v) the number of policemen laid off at intersection v. After the layoff, for every street connecting intersections u and v the totals must exactly satisfy

$$ p(u)-z(u)+p(v)-z(v)=b(u,v) $$

Since the rules do not determine the layoffs uniquely, Byteasar wonders: what are the minimum and maximum possible total numbers of laid‐off policemen (i.e. the sum of all z(v)) that comply with the rules? If there is no upper bound, output Infinity.

inputFormat

The first line contains two integers n and m — the number of intersections and the number of streets.

The second line contains n integers: p(1), p(2), ..., p(n), where p(i) is the number of policemen at intersection i.

Each of the next m lines contains three integers u v b indicating that there is a bidirectional street between intersections u and v with safety threshold b(u,v). It is guaranteed that for every street, p(u)+p(v) ≥ b initially holds.

outputFormat

Output two values separated by a space: the minimum and the maximum total number of laid‐off policemen over all intersections. If the maximum number is unbounded, print Infinity as the second value.

sample

1 0
10

0 Infinity