Ash And Rangoli
Ash has been catching pokemons his entire life. Now he wants a different kick. He heard that BPay is offering rewards on collecting stickers!!
A person has limited stickers like Diya ,Rangoli etc. Ash has got all the stickers except Rangoli. Now he has a lot of friends who are also collecting stickers, some of whom have Rangoli.
Pikachu knows that there are N friends in total and M pairs of friends who can share stickers. To share a sticker between a pair of friends BPay charges some Poké(Pokemon Dollars).
On receiving the Rangoli sticker Ash will get a large reward R but he has to pay the total cost of sharing Rangoli for all the transactions till it reaches him.
There is a good news!! BPay will offer a 100% cashback of cost of sharing sticker between one pair of friends. You can choose which pair of friends can transfer the Rangoli and receive 100% cashback. This cost will not be included in total cost of sharing.
Can you help Ash And Pikachu find the maximum reward they can collect??
If they cannot get a positive reward or if there is no possible way , print -1.
See the sample test for clarity.
Input Format
First line contains R, reward that BPay is offering.
Second line contains N, total number of friends. Friends are numbered from 1 to N. Ash is always friend number 1.
Third line contains M, number of pairs of friends who can share stickers.
Next line contains an array of N integers stating if a friend has Rangoli sticker or not.
0≤arr[i]≤1.
arr[i] = 0, denotes that the friend does not have Rangoli.
arr[i] = 1, denotes that the friend has Rangoli.
arr[1] is always 0 as this is Ash who needs Rangoli.
Following M lines contain three integers (u, v, c) :- friend1 , friend2 and cost of sharing a sticker between them respectively.
Constraints
- 1 ≤ R ≤ 109
- 2 ≤ N ≤ 105
- N-1 ≤ M ≤ 105
- 0 ≤ arr[i] ≤ 1
- 1 ≤ c ≤109
- It is possible to reach from any friend to another
- It is guaranteed that no friend is friend to himself
- It is guaranteed that a particular pair of friends do not appear twice or more in the input
Output Format
Print the maximum reward Ash can collect after paying the total cost of sharing stickers.
Print -1 if he cannot get a positive reward or if there is no possible way to trade Rangoli.
Sample Input 0
1000
6
6
0 0 0 1 1 0
1 2 500
1 3 2
3 4 5
3 2 12
2 5 1
5 6 7
Sample Output 0
999
Explanation 0
- Ash first makes Friend 2 and Friend 5 trade the Rangoli sticker at cost of 1.
- Next he exchanges from Friend 2 and Friend 1(himself), at cost of 500 but applies the 100% cashback.
- So in total he pays cost 1 and gains 1000-1 = 999 Pokedollars
xxxxxxxxxxwith Ada.Text_IO, Ada.Integer_Text_IO;use Ada;procedure Solution is-- Enter your code here. Read input from STDIN. Print output to STDOUTend Solution