How to select a different STAR

[Sidney Schwartz 1]

After much studying of the Book of Words, I tried my first flight in this aircraft. Didn't do too badly! VERY impressive plane. There was one thing I was not able to figure out, though. On receiving clearance at the start of the flight I set up the FMC with the rwys and SID/STAR I was told to expect. While enroute the destination winds changed and I was given a different rwy. Same STAR but different transition for the approach. On the Arrival page I was to select a new runway, but no matter what I tried I could not figure out how to change the STAR that I initially selected. I ended up having to manually delete the final waypoints of the STAR and entering the new ones that would get me to the transition for the new rwy. How do I change the STAR after it's already been entered?