Lets not forget that those "tiny locomotives" were still weighing in at 60,000 lbs and there were lots of them. There was also lots of laborers.
This time frame is also not long before the construction of the Brooklyn bridge, and the Golden Gate. So the technique was out there to handle these large items, over what seems like huge distances. Loggers still striing cables from hill top to hill top to move enormous logs across revines, and that is fairly close to what one could do to move bridge parts.
Now photos of Loboto Bridge being installed would be very interesting!!