input.txt

Luebeck Hamburg 63
Hamburg Bremen 116
Hamburg Hannover 153
Hamburg Berlin 291
Bremen Hannover 132
Bremen Dortmund 234
Hannover Magdeburg 148
Hannover Kassel 165
Magdeburg Berlin 166
Berlin Dresden 204
Dresden Leipzig 119
Leipzig Magdeburg 125
Dortmund Duesseldorf 69
Kassel Frankfurt 185
Frankfurt Dortmund 221
Frankfurt Nuremberg 222
Leipzig Nuremberg 263
Dortmund Saarbruecken 350
Saarbruecken Frankfurt 177
Saarbruecken Karlsruhe 143
Karlsruhe Stuttgart 71
Stuttgart Frankfurt 200
Stuttgart Munich 215
Stuttgart Nuremberg 207
Nuremberg Munich 171
Manchester Birmingham 84
Birmingham Bristol 85
Birmingham London 117
END OF INPUT