Van is a boss of SF Express in Shenzhen. He has \(n\) SF Express sites, these sites are connected by \(m\) streets and the i-th site has wi staffs. To save the cost, Van wants to remove several staffs from them.
However, there is a minimum number of staff requirement in each street, i.e., the j-th street should has at least cj staffs. The number of staffs in the j-th street is the sum of staffs in the two sites which are connected by j-th street.
Now, please tell Van what is the minimum and maximum number of staffs you can remove such that the requirement of each street is exactly satisfied, "exactly" means the sum of the staffs in the two sides connected by j-th street is equal to the minimum number of staff requirement in it. If you cannot find a feasible solution, print “impossible”.
The first line contains two integers the number of SF Express sites \(n(1\leq n\leq 500 000)\) and the number of streets \(m(1\leq m\leq 3 000 000)\)
The second line is divided by a space to give n integers, the i-th integer \(w(0\leq w\leq 10^6)\)representing the number of staves at the i-th site
The next m rows each contain three integers \(u,v(1\leq u,v\leq n)\), \(c(0\leq c\leq 10^6)\), representing the number of staves needed to connect the u-th site and the v-th site in a street of c
Due to the sheer volume of data, even c++ is recommended to use read-in optimisation, something like.
char BB[1<<15],*K=BB,*T=BB;
#define getc() (K==T&&(T=(K=BB)+fread(BB,1,1<<15,stdin),K==T)?0:*K++)
inline long long read()
{
long long x=0;char ch=getc();
while(ch<'0'||ch>'9')ch=getc();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getc();
return x;
}
Using scanf to read in may result in RE