I had Originally thought of using Nicoll-Dyson beams to propel probes and small ships from the Milky Way to as many galaxies as they can reach to turn stars in those galaxies into Shkadov thrusters to return to our galaxy.
The problem with Shkadov thrusters is they have extremely slow initial acceleration due to the mass of the star but once its around a billion years a star like our sun can have moved 35,000 light-years and will be moving at 20 km/s by then.
Nicoll-Dyson beams also have an issue of the beam spreading and being less effective propelling a ship once we get into inter-galactic distances. So I thought since they are arriving home on Shkadov thrusters they could also have left the Milky Way in the same way, at least your massive fuel source isn't millions of light-years away.
For the return journey the majority of stars will be red dwarfs due to their trillions of years life span but they are extremely slow moving stars due to their low energy output so a massive star may be the best bet as even though they are much more massive and harder to move their energy output is magnitudes higher but the major problem with these stars is their short life span.
What makes this calculation even harder is that the two galaxies are moving towards each other and it could be asked why bother traveling there when we will collide in 4 billion years but I would like to arrive in Andromeda long before the merger.
Is there a type of star that could get to Andromeda as a Shkadov thruster long before the merger or could even a Nicoll-Dyson beam using the correct star type propel a probe or small ship all the way to Andromeda in the shorter travel times I am after?
Edit: someone had done some calculations and they said it is not possible to reach Andromeda with a massive star, their calculations put our suns output as being able to reach in 20 billion years and a 10 solar mass star reaching in 1 billion years, both travel times being far longer than their life span but they did have an interesting suggestion of riding the supernova blast for the remaining journey.