The Dragon King X24802

Input

5
DragonValley GreenFields 10 5
DragonValley BlueFields 15 5
DragonValley RedFields 20 5
RedFields DragonEye 5 10
GreenFields DragonEye 16 20

Output

Minimum time: 25
Minimum path: DragonValley RedFields DragonEye

Input

5
DragonValley GreenFields 10 5
DragonValley BlueFields 15 5
DragonValley RedFields 20 5
RedFields DragonEye 5 10
GreenFields DragonEye 15 20

Output

Minimum time: 25
Minimum path: DragonValley GreenFields DragonEye

Input

9
DragonValley GreenFields 10 5
DragonValley BlueFields 15 5
DragonValley RedFields 20 5
RedFields SlimeRock 20 8
GreenFields DragonEye 210 184
SlimeRock BearHills 35 10
BearHills DragonEye 22 22
BlueFields DeepLagoon 34 10
DeepLagoon DragonEye 43 27

Output

Minimum time: 67
Minimum path: DragonValley BlueFields DeepLagoon DragonEye