Dramatic chipmunks P22418

0.76 Mr William and Mr Christopher share a beautiful pear tree of a hybrid Marlowe-Shakes cultivar. It grows right between their neighbouring farms in Avonford-upon-Strat, an even more beautiful village in the middle of the English countryside. Alas, that beauty is marred by the tree’s inhabitation by the most despicable and quarrelling among all zoological species: the dramatic chipmunks.

These mischievous long-toothed chewers spend all day looting the tree’s pears and plotting schemes to steal them from each other. Mr William and Mr Christopher must put up in martyrdom with their high-pitched rodent-voiced discussions:

0.24

– Oh, Rosencrantz, thou long-tailed knave! Wherefore doeth thou steal mine pears?
– Nay, Guilderstern! Voltemand stole thy pears, that cockered motley-minded hugger-mugger.
– Ah, the churlish rascal…And he also stole from that dismal-dreaming low-classed fustilarian, Laertes!
– This mustn’t be true… Laertes stole from Horatio, and Horatio stole from Voltemand himself. For nut’s sake, this impudent stravaganza of debauchery shall not be tolerated in this hallowed tree!
After all plundering, larceny, and bickering, at the end of the day the chipmunks indulge in gluttony and consume the fruits of their pillaging before falling asleep inebriated from their vice.

Can you help Mr William and Mr Christopher figure out how many of their precious pears fall victims of all this unnecessary daily drama?

Input

Input consists of several cases. Each case starts with the number of thefts $n$ and the number of pears $p$ each chipmunk will eat at the end of the day. Both $n$ and $p$ are between 1 and $10^4$. Follow $n$ triples $s$ $t$ $x$ indicating that $s$ stole $x$ pears from $t$, where $s$ and $t$ are words made up of between 1 and 20 letters, and $x$ is an integer between 1 and $10^4$. The robberies are not necessarily given in chronological order. All chipmunks are at least either the subject or the object of an intended theft.

A chipmunk that steals from another one will be considered of lower class than the former. Chipmunks acknowledge this classist relationship transitively, and a higher-class chipmunk should never steal from a lower-class one. When a chipmunks identifies that it could engage in a stealing cycle, it will leave the tree before thefts start, to avoid shaming—even if all other chipmunks are also leaving.

Output

For each case, print the minimum number of pears that would make it possible for the described thefts to happen, and still allow for each chipmunk which did not take part in any cycle to eat (at least) $p$ pears after that.