BZPRO
样例输入1：
10 15
stockholm
amsterdam
london
berlin
copenhagen
oslo
helsinki
dublin
reykjavik
brussels
oslo stockholm 415
stockholm helsinki 396
oslo london 1153
oslo copenhagen 485
stockholm copenhagen 522
copenhagen berlin 354
copenhagen amsterdam 622
helsinki berlin 1107
london amsterdam 356
berlin amsterdam 575
london dublin 463
reykjavik dublin 1498
reykjavik oslo 1748
london brussels 318
brussels amsterdam 173
stockholm amsterdam
oslo london
reykjavik dublin
brussels helsinki
样例输入2：
2 1
first
second
first second 10
first first
first first
second first
first first
样例输出1：
3907
样例输出2：
10
数据范围：
10%或20%的数据中，地图是一棵树。
对于所有数据，
n<=30,m<=1000,w<=10000。