cities_dict = {
    'Beijing': {'Capital': 'China'},
    'Moscow': {'Capital': 'Russia'},
    'Paris': {'Capital': 'France'}
}
for city_key in sorted(cities_dict):
    country = cities_dict[city_key]['Capital']
    print(f"{city_key} is the capital of {country}!")