cities_dict = {'Beijing': {'Capital': 'China'}, 'Moscow': {'Capital': 'Russia'}, 'Paris': {'Capital': 'France'}}

sorted_keys = sorted(cities_dict.keys())

for city in sorted_keys:
    country = cities_dict[city]['Capital']
    print(f"{city} is the capital of {country}!")