Using Python:

Input files:

Case1.txt:

10

A J 18

A H 79

A I 81

J G 24

J F 76

G F 2

G H 50

F E 4

E D 2

D H 20

H C 50

I D 6

I C 97

I J 27

C B 22

Case2.txt:

15

A O 100

A G 16

A C 17

A J 2

O B 100

G E 7

C K 10

C M 5

C J 12

K E 11

K G 33

E O 27

E H 25

E L 6

L B 16

L D 32

H B 24

D B 18

J N 14

M O 24

M F 25

F B 3

N F 31

N I 50

I B 34

I D 19

Case3.txt:

20

A D 30

A E 93

A C 79

C I 10

C E 50

D H 32

D E 50

E H 50

E L 14

E J 88

E I 18

L H 50

L I 69

L F 32

L K 78

I J 63

I F 50

H M 55

H K 71

J G 75

J B 92

J N 57

F J 61

F N 53

F K 28

K G 28

K B 86

G Q 3

G B 100

Q B 50

Q P 50

N B 61

N S 26

M O 79

M R 50

R O 23

R T 14

S R 4

S P 50

S Q 50

T P 32

T N 18

P B 50

P N 50

Solution1.txt:

142

A J G F E D H C B

Solution2.txt:

45

A G E L B

Solution3.txt:

214

A D H K G Q B