import sys

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

for keys1 in sorted(cities_dict.keys()):
    name=cities_dict[keys1]
    print('{} is the capital of {}!'.format(keys1,name['Capital']))