sampleinput.txt

52 77
0 1 400
0 17 200
0 31 500
1 2 100
1 10 300
2 3 50
2 29 50
3 42 75
3 4 25
4 43 25
4 5 25
5 6 200
6 7 100
6 14 150
7 8 50
7 16 150
8 9 25
8 48 25
9 51 250
10 11 275
10 29 75
11 12 200
11 30 75
12 13 50
12 6 50
12 22 100
13 14 50
14 15 75
14 23 125
15 16 75
16 9 225
17 18 200
18 10 50
18 19 50
18 27 100
19 20 50
20 21 150
21 22 150
22 23 250
23 24 375
24 25 375
25 26 375
26 51 375
27 28 100
28 20 100
29 4 25
29 30 100
30 5 175
31 32 350
31 40 150
32 33 150
32 41 200
33 34 450
34 35 475
35 36 200
35 49 200
35 44 75
36 37 200
37 38 200
38 39 150
38 48 50
39 51 150
40 41 150
41 3 50
41 33 300
42 43 50
42 34 25
43 44 75
44 45 150
45 46 250
46 7 100
46 47 150
47 48 250
48 51 325
49 50 100
49 45 100
50 47 100