#P2068. yes,masterghost!(III)

yes,masterghost!(III)

After they fixed the water pipes,they are going to use those water pipes to get out of this hell. But when one of them touch the water, he feel his blood is sucking by the water and shout "help". Luckily, this guy doesn't die. However, they have to find a way to get out. A magician say, it's not water, it's a kind of monster, like slime. A warlock say, "I have a spell, we can suck the monsters' blood back. But if the blood you got is smaller than you lost, you maybe die!". A paladin say,"Don't warry about this, I can keep you alive, and let those monster lose their ability at the same time. ". "How powerful magic!"someone say. "Infact, this magic is a camouflage. Monsters suck my mana instead of your blood." the paladin keep saying.

Luckly, the warlock has figured out how much blood will lose and get if  pass through one pipe(no mater how many people), and every pipe's cost is different. After deliberation, they decide draw apart so that they can get maximum of monsters' blood(because it's pricious) while using the minimum of the paladin's mana.(Guaranteed that they have enough man which means they can visit every pipe)

Imagine that all those pipes consist a net, and our mission is find a way to from point A to point B. Of cause we need cost smallest mana of paladin and get the blood of monsters as much as we can.

Input

multiple test.
the first line has two integers N and M(1<=N<=300,1<=M<=1000)
fowoll M lines,every line has four integers,pa,pb,m,b. Which means from point pa to point pb will cost m mana of paladin and get b blood of the monster.
last line has two integers S and E. Which means they are at point S, and they want to go to point E.

Output

output the maximum of the blood while using the minimum of the mana.

Sample Input

5 7
1 3 3 5
1 3 4 3
1 4 2 3
2 3 1 6
3 5 4 3
4 5 5 2
2 5 3 3
1 5
5 7
1 2 2 1
1 3 1 3
2 3 3 2
2 4 6 5
3 4 2 1
3 5 3 1
4 5 4 3
1 5

Sample Output

34
12

HINT

</p>

Source