Joe Cougar lives in New York City, but he plans to drive to Los Angeles to seek fame and fortune. Joe's funds are limited, so he has decided to spend each night on his trip at a friend's house. Joe has friends in Columbus, Nashville, Louisville, Kansas City, Omaha, Dallas, San Antonio, and Denver. Joe knows that after one day's drive he can reach Columbus, Nashville, or Louisville. After two days of driving, he can reach Kansas City, Omaha, or Dallas. After three days of driving, he can reach San Antonio or Denver. Finally, after four days of driving, he can reach Los Angeles. To minimize the number of miles traveled, where should Joe spend each night of the trip? The actual road mileages between cities are given in the below figure.

Columbus 680 Kansas City 2 580 610 790 550 Denver 8 790 1030 540 New York 900 Nashville 760 Omaha Los Angeles 3 6 10 Stage 1 Stage S 660 940 1390 San Antonio 770 510 1050 790 Stage 4 700 270 Louisville Dallas 4 830 7 Stage 2 Stage 3