Return to statement of the puzzle
It's not hard to write a computer program to solve the puzzle, but it can also be done by hand in an hour or so. Here are some things to consider:
After the first move or two, the odd length roads are unusable, and the graph is broken into 4 pieces: the center, consisting of H, K, P, T, U, and W, and 3 others, attached to the center at H, K, and W. The first or second move carries you from one of the 3 outer pieces to another one along a road of odd length. Somehow you have to get back to the piece you started in.
Large gaps between consecutive primes impose constraints. In particular, the gap of 18 between 523 and 541 can't be crossed, so the total length is at most 523. Some searching shows that there's no solution of length 113 or less, so the path must cross the gap of 14 between 113 and 127, which can only be done on the road from T to U. Working backward from there shows that the path must start at B.
Working forward from 127 gets you to V at 139. Somehow you must get back to H. Working mod 3 shows that you can't get there without an intervening trip to K. And looking at the possible paths from V to K and K to H shows that you must cross from V at 281 to K at 349 and from K at 431 to H at 457.
Filling in the rest of the path is easy.
Several people asked me how I created the puzzle, so I wrote down what I could remember of the process:
I started by listing primes and the gaps between them. I noticed the gaps of 14 from 113 to 127, 293 to 307, and 317 to 331, and the gap of 18 from 523 to 541. So I decided to have the total length be 523 (or as close as I could get) and have just one road of length 14. (I later added another, but it's not usable for the gaps listed above.) I soon came up with the "center", consisting of H, K, P, T, U, and W. Then I decided to build 3 more pieces, attached to the center at H, K, and W, and joined to each other by roads of odd length. I listed the possible trips through the center and decided that the overall structure of the path would be this: Follow an odd-length road from the H-section to the K-section and get to town K at 71. Go through the center, ending at W at 137. Move within the W-section, returning to W at 283. Go through the center, reaching K at 349. Move within the K-section, returning to K at 431. Go through the center, reaching H at 457, and move within the H-section to return to the start at 523.
Next I worked on the W-section. Between 137 and 283, there are 5 gaps of length 10 or 12, so I put in just one road of length 12 and all others of length at most 8. After that, the W-section was pretty much forced.
Building the K-section was troublesome. There had to be a path from K to K, from 349 to 431. But with almost any choice for the odd-length roads joining the K-section to the others, it would be possible to reach K at 79. Note that the primes after 79 and after 349 have similar structure for a while:
79 83 89 97 101 103 107 109 113 127
349 353 359 367 373 379 383 389 397
The first time there's a prime above 349 without a corresponding one above 79 is at 389. So any path starting at K at 349 leads to one starting at 79, giving many opportunities for a solution shorter than 523. (E.g. in the final map, you can follow the route SWUTPUTPKIL, with several short continuations after that; fortunately none take you back to S.) After quite a bit of experimentation, I came up with a usable K-section.
The H-section was easy.
Finally, I experimented with different odd-length connecting roads, to make sure that there were no unwanted short solutions.
I worked mostly by hand, but used a computer to test various choices for the odd lengths and the lengths IJ, MJ, and RS. The main problem was to prevent solutions of length 113 or less.