villes_voisines = {'Maubeuge': [('Valenciennes', 36), ('Le Câteau', 42), ('La Cappelle', 34)], 'Valenciennes': [('Maubeuge', 36), ('Cambrai', 32), ('Arras', 90), ('Lille', 46), ('Le Câteau', 41)], 'Le Câteau': [('Maubeuge', 42), ('Valenciennes', 41), ('Cambrai', 22), ('St Quentin', 38), ('Guise', 27), ('La Cappelle', 32)], 'La Cappelle': [('Maubeuge', 34), ('Le Câteau', 32), ('Guise', 23), ('Vervin', 17), ('Charleville-Mézière', 68)], 'Cambrai': [('Valenciennes', 32), ('Arras', 37), ('St Quentin', 39), ('Le Câteau', 22), ('Bapaume', 30), ('Péronne', 45)], 'Arras': [('Valenciennes', 90), ('Cambrai', 37), ('Lille', 50), ('St Pol/Ternoise', 34), ('Béthune', 30), ('Doullens', 36), ('Bapaume', 22)], 'Lille': [('Valenciennes', 46), ('Arras', 50), ('Dunkerque', 77), ('St Omer', 67), ('Béthune', 38)], 'St Quentin': [('Cambrai', 39), ('Amiens', 74), ('Soissons', 58), ('Laon', 52), ('Le Câteau', 38), ('Guise', 27), ('Péronne', 30), ('Roye', 48), ('Noyon', 40)], 'Bapaume': [('Cambrai', 30), ('Arras', 22), ('Amiens', 48), ('Péronne', 28)], 'Péronne': [('Cambrai', 45), ('Amiens', 44), ('St Quentin', 30), ('Bapaume', 28), ('Roye', 23)], 'Paris': [('Chartres', 82), ('Versailles', 28), ('Beauvais', 76), ('Meaux', 45), ('Fontainebleau', 62), ('Senlis', 44), ('Guignes', 43)], 'Chartres': [('Paris', 82), ('Orléans', 73), ('Le Mans', 107), ('Versailles', 72), ('Dreux', 35), ('Fontainebleau', 97), ('Nogent le Rotrou', 54), ('Châteaudun', 35)], 'Versailles': [('Paris', 28), ('Mantes', 43), ('Chartres', 72), ('Dreux', 50)], 'Beauvais': [('Paris', 76), ('Amiens', 60), ('Rouen', 80), ('Neufchatel en Braye', 58), ('Compiègne', 60), ('Mantes', 69), ('Roye', 67), ('Senlis', 51)], 'Meaux': [('Paris', 45), ('Soissons', 65), ('Sézanne', 77), ('Fontainebleau', 85), ('Senlis', 36), ('Château-Thierry', 47), ('Provins', 74), ('Guignes', 41)], 'Fontainebleau': [('Paris', 62), ('Orléans', 87), ('Chartres', 97), ('Meaux', 85), ('Sens', 53), ('Provins', 36), ('Guignes', 33), ('Montargis', 48)], 'Senlis': [('Paris', 44), ('Compiègne', 32), ('Soissons', 59), ('Beauvais', 51), ('Meaux', 36)], 'Guignes': [('Paris', 43), ('Meaux', 41), ('Fontainebleau', 33), ('Provins', 41)], 'St Pol/Ternoise': [('Arras', 34), ('Hesdin', 20), ('Béthune', 29), ('Doullens', 28)], 'Béthune': [('Arras', 30), ('Lille', 38), ('St Pol/Ternoise', 29), ('St Omer', 44)], 'Doullens': [('Arras', 36), ('Amiens', 32), ('Abbeville', 41), ('St Pol/Ternoise', 28), ('Hesdin', 38)], 'Dunkerque': [('Lille', 77), ('Calais', 43), ('St Omer', 39)], 'St Omer': [('Lille', 67), ('Montreuil/Mer', 52), ('Dunkerque', 39), ('Calais', 40), ('Boulogne/Mer', 44), ('Hesdin', 43), ('Béthune', 44)], 'Reims': [('Soissons', 56), ('Laon', 45), ('Châlons/Marne', 44), ('Sézanne', 70), ('Charleville-Mézière', 73), ('Mazagran', 47), ('Suippes', 42), ('Château-Thierry', 61)], 'Soissons': [('Reims', 56), ('Compiègne', 38), ('St Quentin', 58), ('Laon', 36), ('Sézanne', 83), ('Meaux', 65), ('Senlis', 59), ('Château-Thierry', 35)], 'Laon': [('Reims', 45), ('Soissons', 36), ('St Quentin', 52), ('Guise', 38), ('Vervin', 32), ('Charleville-Mézière', 91)], 'Châlons/Marne': [('Reims', 44), ('Verdun', 97), ('Suippes', 23), ('Vitry le François', 32), ('Sommesous', 27)], 'Sézanne': [('Reims', 70), ('Soissons', 83), ('Troyes', 62), ('Meaux', 77), ('Sens', 79), ('Sommesous', 63), ('Château-Thierry', 48), ('Provins', 42)], 'Charleville-Mézière': [('Reims', 73), ('Laon', 91), ('Verdun', 102), ('La Cappelle', 68), ('Vervin', 69), ('Mazagran', 48), ('Metz', 160)], 'Mazagran': [('Reims', 47), ('Charleville-Mézière', 48), ('Suippes', 31)], 'Suippes': [('Reims', 42), ('Châlons/Marne', 23), ('Verdun', 76), ('Mazagran', 31)], 'Château-Thierry': [('Reims', 61), ('Soissons', 35), ('Sézanne', 48), ('Meaux', 47)], 'Montreuil/Mer': [('Boulogne/Mer', 38), ('Abbeville', 44), ('Hesdin', 23), ('St Omer', 52)], 'Boulogne/Mer': [('Montreuil/Mer', 38), ('Calais', 38), ('St Omer', 44)], 'Abbeville': [('Montreuil/Mer', 44), ('Amiens', 47), ('Dieppe', 65), ('Neufchatel en Braye', 61), ('Hesdin', 30), ('Doullens', 41)], 'Hesdin': [('Montreuil/Mer', 23), ('Abbeville', 30), ('St Pol/Ternoise', 20), ('St Omer', 43), ('Doullens', 38)], 'Calais': [('Dunkerque', 43), ('Boulogne/Mer', 38), ('St Omer', 40)], 'Amiens': [('Neufchatel en Braye', 68), ('St Quentin', 74), ('Beauvais', 60), ('Abbeville', 47), ('Doullens', 32), ('Bapaume', 48), ('Péronne', 44), ('Roye', 41)], 'Neufchatel en Braye': [('Amiens', 68), ('Rouen', 51), ('Dieppe', 36), ('Beauvais', 58), ('Abbeville', 61)], 'Roye': [('Amiens', 41), ('Compiègne', 38), ('St Quentin', 48), ('Beauvais', 67), ('Péronne', 23), ('Noyon', 20)], 'Rouen': [('Dieppe', 61), ('Neufchatel en Braye', 51), ('Evreux', 52), ('Caen', 118), ('Beauvais', 80), ('Le Havre', 82), ('Argentan', 130)], 'Dieppe': [('Rouen', 61), ('Neufchatel en Braye', 36), ('Abbeville', 65), ('Le Havre', 106)], 'Evreux': [('Rouen', 52), ('Mantes', 42), ('Dreux', 42), ('Argentan', 120)], 'Caen': [('Rouen', 118), ('St Lô', 59), ('Vire', 60), ('Argentan', 59), ('Domfront', 78), ('Cherbourg', 120)], 'Le Havre': [('Rouen', 82), ('Dieppe', 106)], 'Argentan': [('Rouen', 130), ('Evreux', 120), ('Caen', 59), ('Alençon', 44), ('Domfront', 55)], 'Compiègne': [('Soissons', 38), ('Beauvais', 60), ('Roye', 38), ('Noyon', 24), ('Senlis', 32)], 'Noyon': [('Compiègne', 24), ('St Quentin', 40), ('Roye', 20)], 'Guise': [('St Quentin', 27), ('Laon', 38), ('Le Câteau', 27), ('La Cappelle', 23), ('Vervin', 25)], 'Vervin': [('Laon', 32), ('Guise', 25), ('La Cappelle', 17), ('Charleville-Mézière', 69)], 'Verdun': [('Châlons/Marne', 97), ('St Dizier', 80), ('Charleville-Mézière', 102), ('Suippes', 76), ('Metz', 65)], 'Vitry le François': [('Châlons/Marne', 32), ('St Dizier', 29), ('Sommesous', 26), ('Brienne le Château', 42)], 'Sommesous': [('Châlons/Marne', 27), ('Troyes', 50), ('Sézanne', 63), ('Vitry le François', 26)], 'Châlons/Saône': [('Mâcon', 54), ('Beaune', 27), ('Autun', 67), ('Dôle', 63), ('Paray le Monial', 89), ('Lons le Saunier', 64), ('Bourg en Bresse', 81)], 'Mâcon': [('Châlons/Saône', 54), ('Lyon', 70), ('Paray le Monial', 78), ('Bourg en Bresse', 34)], 'Beaune': [('Châlons/Saône', 27), ('Auxerre', 158), ('Dijon', 52), ('Autun', 40), ('Dôle', 61)], 'Autun': [('Châlons/Saône', 67), ('Beaune', 40), ('Nevers', 102), ('Paray le Monial', 67)], 'Dôle': [('Châlons/Saône', 63), ('Dijon', 49), ('Beaune', 61), ('Besançon', 46), ('Lons le Saunier', 51)], 'Paray le Monial': [('Châlons/Saône', 89), ('Mâcon', 78), ('Moulins', 52), ('Autun', 67)], 'Lons le Saunier': [('Châlons/Saône', 64), ('Besançon', 77), ('Dôle', 51), ('Genève', 115), ('Bourg en Bresse', 61)], 'Bourg en Bresse': [('Châlons/Saône', 81), ('Mâcon', 34), ('Lons le Saunier', 61), ('Collonges', 80)], 'Lyon': [('St Etienne', 47), ('Mâcon', 70), ('Valence', 83), ('Ambérieu en Bugey', 52), ('Bourgoin Jallieu', 62), ('Roanne', 86), ('Feurs', 68)], 'St Etienne': [('Lyon', 47), ('Clermont Ferrand', 146), ('Valence', 93), ('Le Puy', 77), ('Feurs', 39), ('Thiers', 121)], 'Valence': [('Lyon', 83), ('Grenoble', 94), ('St Etienne', 93), ('Aubenas', 69), ('Montélimar', 46), ('Serres', 138)], 'Ambérieu en Bugey': [('Lyon', 52), ('Chambéry', 79), ('Bourgoin Jallieu', 28)], 'Bourgoin Jallieu': [('Lyon', 62), ('Grenoble', 77), ('Ambérieu en Bugey', 28), ('Chambéry', 45)], 'Roanne': [('Lyon', 86), ('Moulins', 99), ('Feurs', 39), ('Thiers', 70)], 'Feurs': [('Lyon', 68), ('St Etienne', 39), ('Roanne', 39), ('Thiers', 69)], 'Grenoble': [('Valence', 94), ('Chambéry', 57), ('Bourgoin Jallieu', 77), ('Briançon', 116), ('Gap', 103), ('Serres', 109)], 'Chambéry': [('Grenoble', 57), ('Annecy', 44), ('Albertville', 49), ('Ambérieu en Bugey', 79), ('Bourgoin Jallieu', 45)], 'Briançon': [('Grenoble', 116), ('Gap', 87)], 'Gap': [('Grenoble', 103), ('Briançon', 87), ('Serres', 41), ('Sisteron', 43)], 'Serres': [('Grenoble', 109), ('Valence', 138), ('Orange', 105), ('Gap', 41), ('Sisteron', 29)], 'Marseille': [('Aix en Provence', 28), ('Le Luc', 90), ('Toulon', 65), ('Arles', 87)], 'Aix en Provence': [('Marseille', 28), ('Avignon', 75), ('Sisteron', 107), ('Le Luc', 84), ('Arles', 74)], 'Le Luc': [('Marseille', 90), ('Aix en Provence', 84), ('Grasse', 64), ('Toulon', 57)], 'Toulon': [('Marseille', 65), ('Cannes', 129), ('Le Luc', 57)], 'Arles': [('Marseille', 87), ('Avignon', 38), ('Aix en Provence', 74), ('Nimes', 30), ('Montpellier', 73)], 'Font-Romeu': [('Perpignan', 80), ('Foix', 107), ('Quillan', 77)], 'Perpignan': [('Font-Romeu', 80), ('Narbonne', 62), ('Quillan', 75)], 'Foix': [('Font-Romeu', 107), ('Toulouse', 82), ('Carcassonne', 81), ('St Martory', 90), ('Quillan', 62)], 'Quillan': [('Font-Romeu', 77), ('Perpignan', 75), ('Carcassonne', 51), ('Foix', 62)], 'Douarnenez': [('Quimper', 23), ('Pleyben', 27)], 'Quimper': [('Douarnenez', 23), ('Lorient', 66), ('Rostrenen', 72), ('Pleyben', 27)], 'Pleyben': [('Douarnenez', 27), ('Brest', 45), ('Quimper', 27), ('Rostrenen', 62), ('Morlaix', 49)], 'Rennes': [('Nantes', 107), ('Avranches', 80), ('Ploermel', 61), ('Fougères', 48), ('Vitré', 38), ('Châteaubriant', 55), ('Pontchâteau', 92), ('St Meen', 42), ('Dinan', 51)], 'Nantes': [('Rennes', 107), ('Angers', 89), ('Châteaubriant', 66), ('Pontchâteau', 51), ('Chôlet', 57), ('La Roche/Yon', 59)], 'Avranches': [('Rennes', 80), ('St Lô', 56), ('Vire', 50), ('Domfront', 66), ('Cherbourg', 132), ('Fougères', 40), ('Dinan', 70)], 'Ploermel': [('Rennes', 61), ('Lorient', 79), ('Vannes', 47), ('St Meen', 34), ('Loudéac', 43)], 'Fougères': [('Rennes', 48), ('Laval', 48), ('Avranches', 40), ('Vire', 67), ('Mayenne', 44), ('Vitré', 37)], 'Vitré': [('Rennes', 38), ('Laval', 33), ('Fougères', 37), ('Châteaubriant', 45)], 'Châteaubriant': [('Rennes', 55), ('Nantes', 66), ('Laval', 67), ('Angers', 71), ('Vitré', 45)], 'Pontchâteau': [('Rennes', 92), ('Nantes', 51), ('Vannes', 59), ('St Nazaire', 23)], 'St Meen': [('Rennes', 42), ('St Brieuc', 66), ('Ploermel', 34), ('Dinan', 36), ('Loudéac', 43)], 'Dinan': [('Rennes', 51), ('Avranches', 70), ('St Brieuc', 57), ('St Meen', 36)], 'Strasbourg': [('Savernes', 39), ('Lunéville', 50), ('St Dié', 90), ('Colmar', 67)], 'Savernes': [('Strasbourg', 39), ('Sarreguemines', 70), ('Sarrebourg', 30)], 'Lunéville': [('Strasbourg', 50), ('Nancy', 30), ('Château-Salins', 30), ('St Dié', 46)], 'St Dié': [('Strasbourg', 90), ('Lunéville', 46), ('Colmar', 56), ('Epinal', 47)], 'Colmar': [('Strasbourg', 67), ('St Dié', 56), ('Mulhouse', 41)], 'Bourges': [('Vierzon', 33), ('Cosne', 60), ('Châteauroux', 62), ('Montluçon', 93), ('Moulins', 100)], 'Vierzon': [('Bourges', 33), ('Orléans', 79), ('Blois', 75), ('Châteauroux', 58)], 'Cosne': [('Bourges', 60), ('Orléans', 108), ('Auxerre', 74), ('La Charité', 28), ('Clamecy', 54), ('Montargis', 73)], 'Châteauroux': [('Bourges', 62), ('Tours', 111), ('Vierzon', 58), ('Poitiers', 120), ('Limoges', 126), ('Montluçon', 98), ('Selles', 59)], 'Montluçon': [('Bourges', 93), ('Clermont Ferrand', 91), ('Brive la Gaillarde', 182), ('Châteauroux', 98), ('Limoges', 147), ('Moulins', 76)], 'Moulins': [('Bourges', 100), ('Clermont Ferrand', 96), ('Montluçon', 76), ('Nevers', 60), ('Paray le Monial', 52), ('Roanne', 99), ('Thiers', 91)], 'Orléans': [('Chartres', 73), ('Blois', 56), ('Vierzon', 79), ('Fontainebleau', 87), ('Cosne', 108), ('Châteaudun', 48), ('Vendôme', 64), ('Montargis', 72)], 'Blois': [('Orléans', 56), ('Tours', 58), ('Vierzon', 75), ('Vendôme', 32), ('Selles', 39)], 'Châteaudun': [('Orléans', 48), ('Chartres', 35), ('Nogent le Rotrou', 55), ('Vendôme', 39)], 'Vendôme': [('Orléans', 64), ('Tours', 55), ('Le Mans', 77), ('Blois', 32), ('Châteaudun', 39)], 'Montargis': [('Orléans', 72), ('Auxerre', 69), ('Fontainebleau', 48), ('Sens', 51), ('Cosne', 73)], 'Tours': [('Le Mans', 80), ('Blois', 58), ('Châteauroux', 111), ('Poitiers', 104), ('Vendôme', 55), ('Selles', 73), ('La Flèche', 70), ('Saumur', 64)], 'Le Mans': [('Tours', 80), ('Chartres', 107), ('Laval', 69), ('Angers', 92), ('Nogent le Rotrou', 66), ('Alençon', 49), ('Mayenne', 74), ('Vendôme', 77), ('La Flèche', 43)], 'Poitiers': [('Tours', 104), ('Châteauroux', 120), ('Limoges', 121), ('Saumur', 80), ('Doué', 92), ('Niort', 75), ('Civray', 54), ('Parthenay', 50)], 'Selles': [('Tours', 73), ('Blois', 39), ('Châteauroux', 59)], 'La Flèche': [('Tours', 70), ('Le Mans', 43), ('Angers', 48), ('Saumur', 51)], 'Saumur': [('Tours', 64), ('Angers', 54), ('Poitiers', 80), ('La Flèche', 51), ('Doué', 59)], 'Mantes': [('Evreux', 42), ('Versailles', 43), ('Dreux', 46), ('Beauvais', 69)], 'Dreux': [('Mantes', 46), ('Chartres', 35), ('Evreux', 42), ('Versailles', 50), ('Nogent le Rotrou', 65), ('Alençon', 110)], 'Narbonne': [('Perpignan', 62), ('Béziers', 27), ('Carcassonne', 55)], 'Toulouse': [('Carcassonne', 92), ('Montauban', 52), ('Foix', 82), ('Albi', 74), ('Auch', 78), ('St Martory', 72), ('Mazamet', 82)], 'Carcassonne': [('Toulouse', 92), ('Narbonne', 55), ('Foix', 81), ('Mazamet', 49), ('Quillan', 51)], 'Montauban': [('Toulouse', 52), ('Cahors', 61), ('Agen', 72), ('Auch', 86)], 'Albi': [('Toulouse', 74), ('Figeac', 107), ('Millau', 113), ('Rodez', 79), ('Mazamet', 58)], 'Auch': [('Toulouse', 78), ('Montauban', 86), ('Agen', 71), ('Mont de Marsan', 104), ('Lannemezan', 63), ('Tarbes', 73)], 'St Martory': [('Toulouse', 72), ('Foix', 90), ('Lannemezan', 45)], 'Mazamet': [('Toulouse', 82), ('Béziers', 86), ('Carcassonne', 49), ('Millau', 145), ('Albi', 58)], 'Clermont Ferrand': [('St Etienne', 146), ('Brive la Gaillarde', 170), ('Montluçon', 91), ('Moulins', 96), ('Brioude', 69), ('Aurillac', 164), ('Thiers', 44)], 'Brive la Gaillarde': [('Clermont Ferrand', 170), ('Cahors', 100), ('Figeac', 88), ('Limoges', 93), ('Périgueux', 68), ('Montluçon', 182), ('Aurillac', 96)], 'Brioude': [('Clermont Ferrand', 69), ('St Flour', 43), ('Le Puy', 61), ('Aurillac', 104)], 'Aurillac': [('Clermont Ferrand', 164), ('Brive la Gaillarde', 96), ('Figeac', 64), ('Rodez', 90), ('Brioude', 104)], 'Thiers': [('Clermont Ferrand', 44), ('St Etienne', 121), ('Moulins', 91), ('Roanne', 70), ('Feurs', 69)], 'Le Puy': [('St Etienne', 77), ('St Flour', 92), ('Brioude', 61), ('Pradelles', 33), ('Aubenas', 87)], 'Nogent le Rotrou': [('Chartres', 54), ('Le Mans', 66), ('Dreux', 65), ('Alençon', 62), ('Châteaudun', 55)], 'Laval': [('Le Mans', 69), ('Angers', 74), ('Mayenne', 25), ('Fougères', 48), ('Vitré', 33), ('Châteaubriant', 67)], 'Angers': [('Le Mans', 92), ('Nantes', 89), ('Laval', 74), ('Châteaubriant', 71), ('La Flèche', 48), ('Saumur', 54), ('Doué', 41), ('Chôlet', 71)], 'Alençon': [('Le Mans', 49), ('Dreux', 110), ('Nogent le Rotrou', 62), ('Argentan', 44), ('Domfront', 61), ('Mayenne', 61)], 'Mayenne': [('Le Mans', 74), ('Laval', 25), ('Alençon', 61), ('Domfront', 35), ('Fougères', 44)], 'Troyes': [('Auxerre', 81), ('Sézanne', 62), ('Chaumont', 94), ('Sens', 65), ('Châtillon/Saône', 68), ('Sommesous', 50), ('Brienne le Château', 40)], 'Auxerre': [('Troyes', 81), ('Sens', 57), ('Beaune', 158), ('Cosne', 74), ('Clamecy', 43), ('Châtillon/Saône', 85), ('Montargis', 69)], 'Chaumont': [('Troyes', 94), ('St Dizier', 74), ('Châtillon/Saône', 58), ('Neufchâteau', 56), ('Langres', 25)], 'Sens': [('Troyes', 65), ('Auxerre', 57), ('Sézanne', 79), ('Fontainebleau', 53), ('Provins', 34), ('Montargis', 51)], 'Châtillon/Saône': [('Troyes', 68), ('Auxerre', 85), ('Chaumont', 58), ('Dijon', 84)], 'Brienne le Château': [('Troyes', 40), ('St Dizier', 46), ('Vitry le François', 42)], 'Clamecy': [('Auxerre', 43), ('Cosne', 54), ('La Charité', 52), ('Nevers', 69)], 'Nancy': [('Metz', 56), ('Château-Salins', 31), ('Lunéville', 30), ('Epinal', 62), ('Neufchâteau', 59), ('Vittel', 63)], 'Metz': [('Nancy', 56), ('Verdun', 65), ('Charleville-Mézière', 160), ('Sarreguemines', 67), ('Château-Salins', 45)], 'Château-Salins': [('Nancy', 31), ('Metz', 45), ('Sarreguemines', 59), ('Sarrebourg', 43), ('Lunéville', 30)], 'Epinal': [('Nancy', 62), ('St Dié', 47), ('Mulhouse', 110), ('Vittel', 44), ('Belfort', 79), ('Vesoul', 82)], 'Neufchâteau': [('Nancy', 59), ('St Dizier', 82), ('Chaumont', 56), ('Vittel', 33), ('Langres', 69)], 'Vittel': [('Nancy', 63), ('Epinal', 44), ('Neufchâteau', 33), ('Vesoul', 100), ('Langres', 65)], 'St Dizier': [('Verdun', 80), ('Chaumont', 74), ('Vitry le François', 29), ('Brienne le Château', 46), ('Neufchâteau', 82)], 'Aubenas': [('Valence', 69), ('Le Puy', 87), ('Pradelles', 58), ('Montélimar', 41), ('Alès', 74)], 'Montélimar': [('Valence', 46), ('Orange', 56), ('Aubenas', 41)], 'Orange': [('Avignon', 21), ('Nimes', 55), ('Montélimar', 56), ('Serres', 105)], 'Avignon': [('Orange', 21), ('Aix en Provence', 75), ('Nimes', 39), ('Alès', 68), ('Sisteron', 136), ('Arles', 38)], 'Nimes': [('Orange', 55), ('Avignon', 39), ('Montpellier', 52), ('Alès', 44), ('Arles', 30)], 'Alès': [('Avignon', 68), ('Nimes', 44), ('Pradelles', 108), ('Aubenas', 74), ('Mende', 103)], 'Sisteron': [('Avignon', 136), ('Aix en Provence', 107), ('Gap', 43), ('Serres', 29), ('Grasse', 156)], 'Nice': [('Grasse', 31), ('Cannes', 26)], 'Grasse': [('Nice', 31), ('Sisteron', 156), ('Cannes', 17), ('Le Luc', 64)], 'Cannes': [('Nice', 26), ('Grasse', 17), ('Toulon', 129)], 'Montpellier': [('Nimes', 52), ('Béziers', 72), ('Millau', 115), ('Arles', 73)], 'Béziers': [('Montpellier', 72), ('Narbonne', 27), ('Millau', 125), ('Mazamet', 86)], 'Millau': [('Montpellier', 115), ('Béziers', 125), ('St Flour', 141), ('Rodez', 70), ('Albi', 113), ('Mende', 89), ('Mazamet', 145)], 'Cahors': [('Brive la Gaillarde', 100), ('Montauban', 61), ('Figeac', 69), ('Agen', 108)], 'Figeac': [('Brive la Gaillarde', 88), ('Cahors', 69), ('Rodez', 72), ('Albi', 107), ('Aurillac', 64)], 'Limoges': [('Brive la Gaillarde', 93), ('Châteauroux', 126), ('Poitiers', 121), ('Angoulème', 103), ('Périgueux', 102), ('Montluçon', 147), ('Civray', 95)], 'Périgueux': [('Brive la Gaillarde', 68), ('Bordeaux', 124), ('Limoges', 102), ('Angoulème', 86), ('Agen', 138), ('Bergerac', 47)], 'Agen': [('Cahors', 108), ('Montauban', 72), ('Périgueux', 138), ('Bergerac', 91), ('Marmande', 58), ('Auch', 71), ('Mont de Marsan', 112)], 'Bordeaux': [('Angoulème', 91), ('Périgueux', 124), ('Saintes', 93), ('Bergerac', 87), ('Marmande', 84), ('Bayonne', 187)], 'Angoulème': [('Bordeaux', 91), ('Limoges', 103), ('Périgueux', 86), ('Saintes', 70), ('Civray', 56)], 'Saintes': [('Bordeaux', 93), ('Angoulème', 70), ('La Rochelle', 66), ('Niort', 72)], 'Bergerac': [('Bordeaux', 87), ('Périgueux', 47), ('Agen', 91), ('Marmande', 57)], 'Marmande': [('Bordeaux', 84), ('Agen', 58), ('Bergerac', 57), ('Mont de Marsan', 83)], 'Bayonne': [('Bordeaux', 187), ('Mont de Marsan', 97), ('Orthez', 66)], 'Chôlet': [('Nantes', 57), ('Angers', 71), ('Doué', 59), ('La Roche/Yon', 27), ('Parthenay', 72)], 'La Roche/Yon': [('Nantes', 59), ('Chôlet', 27), ('La Rochelle', 85), ('Niort', 85), ('Parthenay', 82)], 'Doué': [('Angers', 41), ('Poitiers', 92), ('Saumur', 59), ('Chôlet', 59), ('Parthenay', 60)], 'St Lô': [('Avranches', 56), ('Caen', 59), ('Cherbourg', 78)], 'Vire': [('Avranches', 50), ('Caen', 60), ('Domfront', 40), ('Fougères', 67)], 'Domfront': [('Avranches', 66), ('Caen', 78), ('Vire', 40), ('Alençon', 61), ('Argentan', 55), ('Mayenne', 35)], 'Cherbourg': [('Avranches', 132), ('Caen', 120), ('St Lô', 78)], 'St Brieuc': [('St Meen', 66), ('Dinan', 57), ('Loudéac', 42), ('Rostrenen', 59), ('Guingan', 34), ('Lannion', 79)], 'Loudéac': [('St Brieuc', 42), ('Lorient', 73), ('Ploermel', 43), ('St Meen', 43), ('Rostrenen', 47)], 'Rostrenen': [('St Brieuc', 59), ('Quimper', 72), ('Lorient', 63), ('Loudéac', 47), ('Guingan', 45), ('Morlaix', 68), ('Pleyben', 62)], 'Guingan': [('St Brieuc', 34), ('Rostrenen', 45), ('Lannion', 32), ('Morlaix', 52)], 'Lannion': [('St Brieuc', 79), ('Guingan', 32), ('Morlaix', 38)], 'Brest': [('Morlaix', 60), ('Pleyben', 45)], 'Morlaix': [('Brest', 60), ('Rostrenen', 68), ('Guingan', 52), ('Lannion', 38), ('Pleyben', 49)], 'Lorient': [('Quimper', 66), ('Vannes', 51), ('Ploermel', 79), ('Loudéac', 73), ('Rostrenen', 63)], 'Vannes': [('Lorient', 51), ('Ploermel', 47), ('Pontchâteau', 59)], 'Provins': [('Sézanne', 42), ('Meaux', 74), ('Fontainebleau', 36), ('Sens', 34), ('Guignes', 41)], 'Langres': [('Chaumont', 25), ('Dijon', 78), ('Neufchâteau', 69), ('Vittel', 65), ('Vesoul', 75)], 'Dijon': [('Beaune', 52), ('Châtillon/Saône', 84), ('Vesoul', 97), ('Besançon', 84), ('Dôle', 49), ('Langres', 78)], 'Vesoul': [('Dijon', 97), ('Epinal', 82), ('Vittel', 100), ('Belfort', 63), ('Besançon', 45), ('Langres', 75)], 'Besançon': [('Dijon', 84), ('Belfort', 90), ('Vesoul', 45), ('Dôle', 46), ('Neufchâtel (Suisse)', 110), ('Lausanne', 127), ('Lons le Saunier', 77)], 'La Charité': [('Cosne', 28), ('Nevers', 24), ('Clamecy', 52)], 'Rodez': [('Figeac', 72), ('Millau', 70), ('St Flour', 175), ('Albi', 79), ('Aurillac', 90)], 'St Flour': [('Millau', 141), ('Rodez', 175), ('Brioude', 43), ('Le Puy', 92), ('Mende', 109)], 'Mende': [('Millau', 89), ('St Flour', 109), ('Pradelles', 59), ('Alès', 103)], 'Niort': [('Poitiers', 75), ('La Roche/Yon', 85), ('La Rochelle', 61), ('Saintes', 72), ('Civray', 56), ('Parthenay', 42)], 'Civray': [('Poitiers', 54), ('Limoges', 95), ('Angoulème', 56), ('Niort', 56)], 'Parthenay': [('Poitiers', 50), ('Doué', 60), ('Chôlet', 72), ('La Roche/Yon', 82), ('Niort', 42)], 'Mont de Marsan': [('Agen', 112), ('Marmande', 83), ('Auch', 104), ('Pau', 77), ('Orthez', 54), ('Bayonne', 97)], 'Nevers': [('Moulins', 60), ('La Charité', 24), ('Clamecy', 69), ('Autun', 102)], 'St Nazaire': [('Pontchâteau', 23)], 'La Rochelle': [('La Roche/Yon', 85), ('Saintes', 66), ('Niort', 61)], 'Lannemezan': [('Auch', 63), ('Tarbes', 36), ('St Martory', 45)], 'Tarbes': [('Auch', 73), ('Lannemezan', 36), ('Pau', 40)], 'Pau': [('Mont de Marsan', 77), ('Tarbes', 40), ('Orthez', 41)], 'Orthez': [('Mont de Marsan', 54), ('Pau', 41), ('Bayonne', 66)], 'Pradelles': [('Le Puy', 33), ('Aubenas', 58), ('Mende', 59), ('Alès', 108)], 'Sarreguemines': [('Metz', 67), ('Château-Salins', 59), ('Savernes', 70), ('Sarrebourg', 59)], 'Sarrebourg': [('Sarreguemines', 59), ('Château-Salins', 43), ('Savernes', 30)], 'Mulhouse': [('Colmar', 41), ('Epinal', 110), ('Belfort', 41)], 'Belfort': [('Mulhouse', 41), ('Epinal', 79), ('Vesoul', 63), ('Besançon', 90)], 'Neufchâtel (Suisse)': [('Besançon', 110), ('Lausanne', 69)], 'Lausanne': [('Besançon', 127), ('Neufchâtel (Suisse)', 69), ('Genève', 38)], 'Genève': [('Lausanne', 38), ('Lons le Saunier', 115), ('Collonges', 30), ('Annecy', 44), ('Bonneville', 21)], 'Collonges': [('Genève', 30), ('Bourg en Bresse', 80), ('Annecy', 41)], 'Annecy': [('Genève', 44), ('Collonges', 41), ('Bonneville', 16), ('Albertville', 46), ('Chambéry', 44)], 'Bonneville': [('Genève', 21), ('Annecy', 16), ('Megève', 43)], 'Albertville': [('Annecy', 46), ('Megève', 23), ('Chambéry', 49)], 'Megève': [('Bonneville', 43), ('Albertville', 23)]}
coordonnees = {'Abbeville': (532, 110), 'Agen': (433, 754), 'Aix en Provence': (815, 825), 'Albertville': (877, 600), 'Albi': (554, 784), 'Alençon': (403, 290), 'Alès': (705, 760), 'Ambérieu en Bugey': (800, 557), 'Amiens': (565, 132), 'Angers': (353, 395), 'Angoulème': (400, 594), 'Annecy': (860, 560), 'Argentan': (396, 258), 'Arles': (750, 813), 'Arras': (599, 89), 'Aubenas': (728, 710), 'Auch': (428, 815), 'Aurillac': (572, 677), 'Autun': (712, 454), 'Auxerre': (658, 361), 'Avignon': (764, 781), 'Avranches': (300, 260), 'Bapaume': (605, 110), 'Bayonne': (263, 825), 'Beaune': (743, 450), 'Beauvais': (549, 185), 'Belfort': (903, 375), 'Bergerac': (423, 682), 'Besançon': (846, 417), 'Béthune': (590, 65), 'Béziers': (639, 850), 'Blois': (492, 387), 'Bonneville': (877, 587), 'Bordeaux': (341, 683), 'Boulogne/Mer': (517, 40), 'Bourg en Bresse': (787, 532), 'Bourges': (573, 440), 'Bourgoin Jallieu': (797, 600), 'Brest': (70, 278), 'Briançon': (903, 670), 'Brienne le Château': (728, 295), 'Brioude': (647, 635), 'Brive la Gaillarde': (505, 649), 'Caen': (374, 209), 'Cahors': (497, 729), 'Calais': (535, 15), 'Cambrai': (630, 100), 'Cannes': (940, 819), 'Carcassonne': (570, 865), 'Châlons/Marne': (712, 235), 'Châlons/Saône': (756, 472), 'Chambéry': (847, 600), 'Charleville-Mézière': (737, 145), 'Chartres': (505, 293), 'Château-Salins': (870, 245), 'Château-Thierry': (643, 225), 'Châteaubriant': (293, 362), 'Châteaudun': (494, 332), 'Châteauroux': (518, 470), 'Châtillon/Saône': (732, 356), 'Chaumont': (773, 325), 'Cherbourg': (282, 155), 'Chôlet': (326, 437), 'Civray': (402, 542), 'Clamecy': (655, 400), 'Clermont Ferrand': (625, 582), 'Collonges': (835, 540), 'Colmar': (937, 322), 'Compiègne': (602, 186), 'Cosne': (612, 404), 'Epinal': (870, 314), 'Evreux': (482, 228), 'Dieppe': (478, 130), 'Dijon': (770, 410), 'Dinan': (248, 280), 'Dôle': (808, 435), 'Domfront': (350, 270), 'Douarnenez': (79, 310), 'Doué': (372, 427), 'Doullens': (567, 105), 'Dreux': (496, 260), 'Dunkerque': (565, 7), 'Feurs': (737, 590), 'Figeac': (544, 709), 'Foix': (510, 890), 'Font-Romeu': (542, 940), 'Fontainebleau': (593, 297), 'Fougères': (309, 296), 'Gap': (861, 708), 'Genève': (860, 530), 'Grasse': (932, 806), 'Grenoble': (828, 640), 'Guignes': (600, 270), 'Guingan': (167, 262), 'Guise': (660, 132), 'Hesdin': (546, 80), 'La Cappelle': (680, 125), 'La Charité': (620, 429), 'La Flèche': (389, 372), 'La Roche/Yon': (284, 480), 'La Rochelle': (300, 535), 'Langres': (786, 355), 'Lannemezan': (411, 871), 'Lannion': (147, 245), 'Laon': (660, 168), 'Lausanne': (893, 490), 'Laval': (339, 329), 'Le Câteau': (652, 108), 'Le Havre': (406, 175), 'Le Luc': (885, 835), 'Le Mans': (410, 338), 'Le Puy': (687, 661), 'Lille': (617, 50), 'Limoges': (485, 576), 'Lons le Saunier': (812, 480), 'Lorient': (145, 353), 'Loudéac': (195, 310), 'Lunéville': (871, 269), 'Lyon': (761, 582), 'Mâcon': (756, 521), 'Mantes': (522, 230), 'Marmande': (423, 682), 'Marseille': (805, 850), 'Maubeuge': (683, 89), 'Mayenne': (351, 303), 'Mazagran': (728, 187), 'Mazamet': (570, 836), 'Meaux': (608, 235), 'Megève': (895, 562), 'Mende': (658, 721), 'Metz': (845, 213), 'Millau': (626, 765), 'Mont de Marsan': (343, 786), 'Montargis': (596, 341), 'Montauban': (490, 775), 'Montélimar': (755, 714), 'Montluçon': (588, 520), 'Montpellier': (690, 819), 'Montreuil/Mer': (515, 63), 'Morlaix': (119, 260), 'Moulins': (642, 497), 'Mulhouse': (938, 358), 'Nancy': (843, 258), 'Nantes': (276, 420), 'Narbonne': (621, 866), 'Neufchâteau': (813, 297), 'Neufchâtel (Suisse)': (912, 440), 'Neufchatel en Braye': (503, 150), 'Nevers': (628, 453), 'Nice': (958, 797), 'Nimes': (729, 792), 'Niort': (355, 520), 'Nogent le Rotrou': (456, 304), 'Noyon': (615, 165), 'Orange': (764, 758), 'Orléans': (533, 350), 'Orthez': (310, 830), 'Paray le Monial': (732, 510), 'Paris': (567, 246), 'Parthenay': (373, 485), 'Pau': (351, 851), 'Périgueux': (442, 647), 'Péronne': (610, 135), 'Perpignan': (615, 920), 'Pleyben': (100, 297), 'Ploermel': (219, 338), 'Poitiers': (415, 495), 'Pontchâteau': (240, 391), 'Pradelles': (688, 691), 'Provins': (638, 280), 'Quillan': (556, 900), 'Quimper': (95, 322), 'Reims': (689, 202), 'Rennes': (272, 323), 'Roanne': (697, 571), 'Rodez': (587, 739), 'Rostrenen': (153, 300), 'Rouen': (478, 185), 'Roye': (600, 154), 'Saintes': (340, 582), 'Sarrebourg': (911, 250), 'Sarreguemines': (910, 210), 'Saumur': (388, 418), 'Savernes': (935, 249), 'Selles': (517, 420), 'Senlis': (585, 210), 'Sens': (637, 319), 'Serres': (835, 723), 'Sézanne': (667, 262), 'Sisteron': (853, 750), 'Soissons': (640, 189), 'Sommesous': (705, 258), 'St Brieuc': (198, 274), 'St Etienne': (725, 615), 'St Dié': (907, 300), 'St Dizier': (758, 269), 'St Flour': (626, 664), 'St Lô': (320, 213), 'St Martory': (453, 870), 'St Meen': (231, 310), 'St Nazaire': (225, 408), 'St Omer': (561, 39), 'St Pol/Ternoise': (567, 82), 'St Quentin': (636, 137), 'Strasbourg': (960, 265), 'Suippes': (726, 215), 'Tarbes': (387, 860), 'Thiers': (657, 571), 'Toulon': (855, 869), 'Toulouse': (498, 820), 'Tours': (445, 405), 'Troyes': (695, 308), 'Valence': (766, 672), 'Valenciennes': (650, 82), 'Vannes': (190, 365), 'Vendôme': (473, 362), 'Verdun': (787, 210), 'Versailles': (553, 252), 'Vervin': (679, 139), 'Vesoul': (853, 375), 'Vierzon': (545, 426), 'Vire': (335, 243), 'Vitré': (308, 320), 'Vitry le François': (730, 259), 'Vittel': (834, 312)}