14691469 SUSTech Online Judge
Problem 1469 --Layoffs

1469: Layoffs

Time Limit: 4 Sec  Memory Limit: 256 MB
Submit: 368  Solved: 82
[Submit][Status][Web Board]

Description

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”.



Input

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


Output

If a solution exists, output the minimum and maximum values separated by spaces, otherwise print "impossible"

Sample Input

3 2
5 10 5
1 2 5
2 3 3

Sample Output

12 15

HINT


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

Source

 

[Submit][Status]