Bon Dieu!
Vous ne savez pas beaucoup de l'Ouest Americain.
I regret to inform you that you are unlikely to have good conditions anywhere if you start on May 1.
North of New Mexico it snows into May and often into June at higher elevations in the Rockies.
Plus, there is the snow from all winter to melt out.
The snowpack this year is above average in much of the West
I know because I have lived in Wyoming and Montana for 30 years.
I also cycled extensively in the high country.
Most of the roads that are part of the GDMBR have very little maintenance and are unpaved.
Thus, the snow has to melt out by itself and the mud has to dry.
(Bicycle parts - like chains and gears - do not work well caked in mud.)
What is more, there will be very few facilities open in national parks and national forests.
Most do not open until the end of May - some not until late June.
Be aware that bears come out of hibernation in April and are actively seeking food.
All of the GDMBR route is black bear country and the northern half is grizzly country.
Since your climate info is limited, I am concerned you may not know grizzly camping protocols.
It sounds like you already have you plane tickets - so the date is fixed.
You will like have high temperatures in 10-15C range with lows often below 0C.
May is also a rainy month with considerable variation between nice and stormy.
(Rain in the valleys in May is usually snow in the mountains.)
<<<>>>
I would strongly urge you not to attempt the actual GDMBR in May.
Climate averages for mid-May in Breckinridge, Colorado are:
High 12C, Low -5C - - - For all of May Precip 5 cm, Snow 25 cm.
You would be far better off to stay in the valleys on pavement.
(Trust me - spring riding in the snow/mud in the Rockies is impossible.)
You can ride the historic High Road from Espanola to Taos, NM
Then ride north via San Luis to Great Sand Dunes.
Connect with the TransAm in Salida and ride all the way to Yellowstone.
Then take US Highway 89 north to Glacier NP.
Going to the Sun Road in Glacier will probably not be open.
But the east side of GTTS is spectacular and Many Glacier area will be accessible.
There may be warm sunny periods where you are tempted to get off road.
Be extremely cautious since you may get trapped in mud with no other traffic.
Also, the warm spells are often followed by late snow storms.
Be glad to give you more info - J