cities_dict = {'Beijing': {'Capital': 'China'}, 'Moscow': {'Capital': 'Russia'}, 'Paris': {'Capital': 'France'}}
key_list = sorted(list(cities_dict.keys()))
for city in key_list:
    print('{} is the capital of {}!'.format(city, cities_dict.get(city, {}).get('Capital')))