1185  SCUE
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 183
Solved: 51
 Description
 There are N citys in RAIN's country.
And there are M directed road between the N citys.
Now she is in the city 0.
And she want to go to city N1.
But the bad FGJ donot want RAIN go to city N1.
He can destroy some city to make it.
RAIN cannot go to the city which be destroyed.
Eeah city has a weight Wi to destroy.
FGJ cannot destroy the city 0.
Can you tell FGJ the minimal totle weight he must destroy?  Input
 The first line of the input is the number of test cases.
For each case there is M+1 lines.
The first line contains two integers N M.
The second line contains N1 integers Wi ( 1 <= i < N ).
The next M lines each contains two integers P and Q,
represent there is a road from city P to city Q.
( 2 <= N <= 1000 , 0 <= M <= 10^5 , 0 <= P,Q < N , 0 <= Wi <= 10^5 )
There is a blank line before each test case.  Output
 For each test case output the answer on a line:
The minimal totle weight FGJ must destroy.  sample input

5 2 0 100 2 1 100 0 1 2 1 100 1 0 2 5 100 0 1 0 1 1 0 0 0 1 1 3 2 1 100 0 1 1 2
 sample output

0 100 0 100 1
 hint
 source
 SCUPC