Description

When global security is threatened by Loki, Nick Fury and his team will need a team to protect the world from disaster. So he created S.H.I.E.L.D, an international peace keeping agency. He is director of S.H.I.E.L.D. And then he find some super human to organize The Avengers, including Tony Stark a.k.a. the Iron Man, Steve Rogers, a.k.a. Captain America, Bruce Banner, a.k.a. The Hulk, Thor; Natasha Romanoff, a.k.a. Black Widow and so on. After beating Loki, they become a real team -- The Avengers!

Though Loki was defeated, Nick Fury think this thing is just a start, not the end. But these superhero’s residences are different, like Thor. So if the world need The Avengers, they can’t assemble quickly. Stack think he can build some way which is The Avengers’ exclusive. Thor don’t agree his idea because his hometown is far away from the earth. Stack can’t build way in the universe. Thor shows that he will send his soldiers to build some Transmission devices like Bifrost. Stack insist that the freeway is cheaper and more convenient to build, though he is not mind the cost.

Now they have an argument. Rogers calm them and let Stack and Thor calculate the cost by their idea, and he will find out the best solution. Because their conditions are different, so maybe sometimes they won’t cost anything but earn something. For example, when Stack build his way to Wakanda, T'Challa not only don’t use Stack’s material, but also give some Vibranium for Stack. By Stack’s calculate, he write all the way he can build and these way’s cost.(If Stack earn, he will write a minus.) As for Thor, Bifrost is a Transmission device, so if one city build a Bifrost, this city can transmit to another city which have built a Bifrost. So he just write the cost in every residences. But Bifrost’s material only Thor have in this world. So Thor can’t earn anything from other heroes.And because of some zone is special, these zone can’t use Bifrost.(If Thor can’t build Bifrost, he will write “$-1$”)

Just when Rogers plan to calculate the best solution. He receive a bad news -- HYDRA is coming. So he must set off now! He give you this task, please give him a best solution. Believe yourself! You can be a superhero, you can be an avenger!

The Avengers, Assemble! Please quickly!

Format

Input

Input contains multiple test cases.

The first line contains two integer numbers N and M (1 <= N <= 10000, 1 <= M <= 100000). N means the number of superhero(their residences are different with each other).Their residences are numbered from 1 to N. M means the number of the way which Stack can build.

Each of the following M lines contains three integer numbers $A, B$ and $C (1 <= A, B <= N, -1000 <= C <= 1000)$. It shows that there can build a way from $A$ residence to $B$ residence with cost $C$.

The last line consists of N integer numbers $w_i(-1 <= w_i <= 1000)$.It means the Bifrost built in $i-th$ city with cost $w_i$.

(I promise that all superheroes must have a way can assemble.)

Output

A single line consisting of a single integer number -- the Minimum cost.(If there is a solution can earn and solve this problem, output a minus means the gains.)

Samples

6 10
1 2 3
2 1 1
5 6 10
1 5 8
2 5 6
1 3 7
3 4 -3
2 4 9
6 4 12
2 3 2
-1 -1 10 20 1 1

8

Hints

For sample, Stack build the 2-th, 5-th, 7-th, 10-th way, and Thor build Bifrost in 5-th, 6-th city.
图是双向边，不是单向边！