uva10099測資A

Input:
7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99
8 9
1 3 25
1 4 15
2 5 22
2 7 9
3 5 34
3 8 20
4 5 15
4 6 28
6 7 11
1 8 150
8 14
1 3 25
1 4 5
1 5 25
2 5 22
2 7 9
2 8 20
3 5 34
3 6 20
3 8 32
4 5 15
4 6 28
4 8 22
6 7 11
7 8 70
2 8 100
10 12
7 10 40
2 7 8
7 9 28
6 10 52
4 10 43
3 10 32
1 8 39
2 10 15
1 9 23
5 9 49
3 5 6
1 6 23
4 5 69
100 500
1 12 74
1 34 50
1 39 25
1 50 83
1 51 57
1 60 24
1 61 70
1 68 57
1 75 66
1 78 55
1 79 79
1 99 57
2 7 62
2 10 22
2 26 83
2 27 17
2 36 51
2 40 16
2 41 48
2 65 60
2 70 35
2 75 42
2 78 38
2 86 44
2 94 87
3 5 84
3 8 13
3 18 20
3 21 72
3 22 35
3 24 70
3 25 81
3 77 12
3 96 66
4 17 70
4 25 51
4 28 88
4 29 49
4 33 58
4 45 22
4 48 26
4 69 71
4 82 35
4 83 46
4 85 24
5 12 21
5 31 59
5 36 37
5 40 87
5 47 26
5 49 38
5 71 40
5 76 54
5 77 45
5 78 46
5 79 79
5 89 48
5 91 33
5 93 83
5 94 53
5 97 71
5 99 43
6 7 64
6 11 27
6 24 75
6 48 71
6 53 29
6 56 77
6 58 20
6 60 87
6 79 89
7 49 18
7 51 74
7 73 14
7 98 53
8 11 87
8 22 20
8 32 12
8 39 54
8 41 81
8 49 35
8 53 26
8 66 76
8 68 27
8 86 72
8 98 20
9 20 23
9 32 24
9 44 23
9 46 82
9 49 86
9 58 76
9 65 34
9 75 86
9 76 54
9 85 87
9 87 46
9 88 54
10 22 80
10 23 39
10 33 50
10 36 28
10 50 24
10 58 36
10 65 28
10 100 31
11 12 36
11 21 11
11 26 33
11 36 26
11 48 28
11 57 73
11 59 34
11 68 77
11 71 68
11 74 26
11 76 28
11 77 64
11 89 18
12 29 47
12 41 24
12 48 56
12 52 80
12 57 16
12 78 13
13 23 19
13 43 19
13 44 52
13 51 55
13 57 44
13 90 39
13 91 80
14 16 10
14 21 83
14 27 82
14 28 65
14 38 26
14 66 21
14 74 44
14 84 80
14 89 76
14 92 43
14 94 34
14 97 37
15 23 71
15 36 79
15 49 68
15 80 62
16 21 40
16 34 85
16 50 56
16 64 37
16 66 88
16 80 77
16 86 79
16 87 23
16 98 26
17 18 41
17 19 37
17 30 11
17 46 57
17 53 11
17 54 33
17 97 45
17 99 64
18 19 41
18 29 21
18 31 72
18 35 21
18 83 62
18 100 62
19 24 38
19 32 67
19 72 86
19 74 29
19 89 84
19 90 46
19 96 72
20 31 40
20 48 70
20 59 54
20 63 48
20 81 20
20 91 69
20 93 40
21 27 35
21 31 13
21 37 28
21 42 51
21 54 64
21 70 46
21 71 62
21 76 61
21 77 31
21 79 67
21 86 69
21 92 28
22 23 50
22 27 43
22 34 36
22 48 19
22 49 42
22 84 70
22 87 26
22 91 17
23 25 68
23 51 21
23 53 87
23 58 59
23 61 57
23 76 65
23 80 50
23 84 14
23 98 77
24 29 33
24 45 70
24 54 58
24 73 60
24 90 43
24 91 25
24 93 37
25 37 58
25 40 50
25 41 73
25 47 53
25 48 58
25 56 88
25 78 26
25 84 79
25 95 51
25 96 89
26 50 40
26 89 84
26 92 15
27 33 28
27 35 45
27 36 34
27 62 29
27 78 79
27 85 69
28 38 66
28 40 29
28 48 89
28 56 50
28 63 69
28 70 74
28 78 34
29 31 24
29 47 88
29 64 50
30 31 48
30 53 34
30 77 83
30 84 26
30 86 73
30 99 68
31 34 33
31 59 79
31 60 47
31 62 25
31 68 25
31 79 80
31 83 17
31 88 83
32 42 71
32 46 52
32 65 77
32 79 38
32 80 58
32 83 23
32 93 57
32 99 25
33 39 24
33 42 36
33 44 56
33 54 76
33 71 56
33 78 31
33 79 33
33 91 37
33 98 87
34 35 81
34 45 45
34 50 79
34 53 57
34 79 86
34 94 51
34 95 81
34 96 27
35 46 38
35 48 34
35 49 24
35 57 27
35 59 18
35 61 67
35 64 40
35 73 53
35 76 87
35 77 61
36 45 38
36 46 12
36 50 66
36 66 34
36 71 81
36 74 30
36 81 26
36 89 31
37 38 41
37 39 48
37 56 14
37 60 84
37 61 73
37 66 10
37 75 59
37 76 56
37 79 52
38 42 59
38 43 26
38 45 15
38 51 40
38 88 79
39 40 42
39 41 49
39 42 85
39 49 68
39 52 86
39 64 87
39 66 33
39 71 70
39 87 47
40 41 53
40 62 59
40 72 84
40 73 72
40 84 52
40 91 69
40 95 31
40 96 15
40 99 16
41 50 68
41 51 24
41 54 17
41 60 47
41 67 32
41 68 73
41 74 26
41 84 61
41 85 62
41 90 31
42 69 68
42 71 82
42 73 29
43 44 41
43 64 15
43 69 66
43 74 79
43 90 13
43 98 22
44 52 17
44 57 22
44 59 81
44 61 15
44 75 42
44 78 59
44 80 18
44 86 27
45 51 26
45 57 86
45 61 27
45 63 62
45 82 13
46 56 21
46 61 62
46 66 58
46 67 41
46 81 20
46 83 45
46 90 48
47 70 19
47 77 83
47 91 16
47 93 43
47 100 89
48 50 71
48 52 32
48 65 75
48 70 65
48 72 50
48 95 73
49 58 48
49 59 16
49 70 56
49 99 21
49 100 27
50 53 36
50 60 42
50 65 11
50 68 32
50 81 51
50 84 80
50 93 63
50 96 45
51 58 28
51 61 81
51 95 26
51 97 55
51 99 44
52 81 19
52 95 29
53 55 12
53 71 53
53 77 29
53 95 24
53 98 11
53 99 31
54 58 28
54 62 55
54 68 60
54 79 63
54 80 11
54 81 20
54 90 15
54 94 52
55 73 70
55 77 77
55 87 50
55 95 30
56 61 44
56 63 74
56 65 74
56 85 21
57 64 45
58 73 85
58 84 32
58 89 65
59 63 57
59 71 55
59 75 70
59 76 54
59 80 26
59 87 66
60 86 61
60 92 55
60 98 72
61 88 68
62 68 54
62 69 43
62 86 17
63 64 47
63 95 20
64 65 83
64 70 89
64 72 72
64 73 19
64 87 25
64 96 54
65 67 48
65 70 56
65 89 70
65 92 41
66 90 82
67 69 70
67 85 16
67 86 44
67 87 36
68 79 85
68 97 66
70 71 69
70 81 51
71 87 62
71 91 72
71 96 55
72 83 47
72 84 38
73 82 20
73 88 73
74 76 23
74 78 23
74 92 62
74 98 19
75 93 43
76 87 42
77 84 79
79 82 65
79 99 75
81 100 39
82 88 30
83 92 26
83 98 38
85 92 33
86 93 10
86 96 13
87 90 18
88 94 89
89 92 84
90 94 76
90 95 21
90 97 82
94 100 59
95 96 76
15 79 2000
100 800
1 11 83
1 16 26
1 19 20
1 25 28
1 33 24
1 47 38
1 48 84
1 53 70
1 65 69
1 68 89
1 75 61
1 76 86
1 77 52
1 78 80
1 95 46
1 96 63
1 97 42
1 99 89
2 4 14
2 8 29
2 11 62
2 14 19
2 21 56
2 31 22
2 40 73
2 41 32
2 48 83
2 51 23
2 53 22
2 69 85
2 70 29
2 73 80
2 75 26
2 79 17
2 83 36
2 87 30
3 8 45
3 9 65
3 12 50
3 23 69
3 29 47
3 44 88
3 74 88
3 76 33
3 77 54
3 78 23
3 82 86
3 91 42
3 94 43
3 95 71
4 5 44
4 8 73
4 10 23
4 18 51
4 19 14
4 20 87
4 29 60
4 31 76
4 40 51
4 42 87
4 43 81
4 53 16
4 63 67
4 69 32
4 74 48
4 78 69
4 79 16
4 80 44
4 89 24
4 91 66
4 96 30
4 97 45
4 98 20
5 24 57
5 38 58
5 45 34
5 56 68
5 63 52
5 65 13
5 69 34
5 82 36
5 92 30
5 94 18
5 95 53
6 15 41
6 18 80
6 20 42
6 21 27
6 25 82
6 30 19
6 31 66
6 32 60
6 33 21
6 49 73
6 50 79
6 56 44
6 72 28
6 74 57
6 78 48
6 88 50
6 98 45
6 99 11
7 14 32
7 17 43
7 22 69
7 29 10
7 33 21
7 35 48
7 56 19
7 57 22
7 59 29
7 75 54
7 76 71
7 77 47
7 78 73
7 100 83
8 23 68
8 33 67
8 34 72
8 38 36
8 44 62
8 47 34
8 50 72
8 69 87
8 70 22
8 72 85
8 86 50
8 88 53
8 90 26
8 97 16
8 99 87
9 11 52
9 13 71
9 21 81
9 23 41
9 30 26
9 33 18
9 53 36
9 58 67
9 66 39
9 72 80
9 73 66
9 84 60
9 93 25
9 94 37
9 97 88
10 13 64
10 26 18
10 34 24
10 36 24
10 55 82
10 74 86
10 90 43
10 93 43
11 12 75
11 13 14
11 19 30
11 24 69
11 26 45
11 35 71
11 37 71
11 58 41
11 80 54
11 83 82
11 84 25
11 86 77
11 91 68
11 94 18
11 95 55
11 99 10
12 13 14
12 26 18
12 34 42
12 35 50
12 37 39
12 38 58
12 39 25
12 48 41
12 50 62
12 51 82
12 63 74
12 64 10
12 87 83
12 88 27
12 91 22
12 94 11
12 100 26
13 15 86
13 16 87
13 20 22
13 26 29
13 29 87
13 30 64
13 31 35
13 39 77
13 53 77
13 54 34
13 58 47
13 59 40
13 58 86
13 82 48
13 95 63
14 35 67
14 40 58
14 66 49
14 79 58
14 86 77
14 93 60
14 94 35
15 25 44
15 29 79
15 37 40
15 39 39
15 40 47
15 45 55
15 46 62
15 48 89
15 49 85
15 52 46
15 53 35
15 62 63
15 71 79
15 73 18
15 76 19
15 79 58
15 84 72
15 85 10
15 87 19
15 89 65
15 94 18
15 97 17
15 99 35
16 24 71
16 32 85
16 34 14
16 42 83
16 44 79
16 61 20
16 66 72
16 67 56
16 71 57
16 77 24
16 84 56
16 86 62
16 88 57
16 95 64
17 21 78
17 32 56
17 35 72
17 36 40
17 44 23
17 55 32
17 69 32
17 81 76
17 85 36
17 87 20
18 31 29
18 35 42
18 44 77
18 45 81
18 61 43
18 63 22
18 95 10
18 96 78
18 97 17
19 26 32
19 37 31
19 51 69
19 53 55
19 54 33
19 70 53
19 77 24
19 80 80
19 85 78
19 92 48
19 93 21
20 22 26
20 28 52
20 35 81
20 42 35
20 45 53
20 46 79
20 47 13
20 48 51
20 59 58
20 60 62
20 63 57
20 64 32
20 69 29
20 71 59
20 72 72
20 73 69
20 84 55
20 87 15
20 99 27
21 27 80
21 28 75
21 30 56
21 34 86
21 58 35
21 59 21
21 63 44
21 68 41
21 76 12
21 89 22
22 29 28
22 33 66
22 36 53
22 48 85
22 67 40
22 70 29
22 80 40
22 86 70
22 97 55
22 99 53
23 51 25
23 55 77
23 69 14
23 72 72
23 80 32
23 85 14
23 88 72
23 89 38
23 93 22
23 97 75
24 30 40
24 34 50
24 43 84
24 46 27
24 52 86
24 59 68
24 77 36
24 80 42
24 81 63
24 83 12
24 84 47
24 91 32
24 93 32
24 95 87
25 26 82
25 35 66
25 39 71
25 48 43
25 50 34
25 63 60
25 65 85
25 67 46
25 71 84
25 74 74
25 75 52
25 77 60
25 81 48
25 89 89
25 91 42
25 96 59
25 98 24
26 29 70
26 30 11
26 38 79
26 54 89
26 58 71
26 67 58
26 70 20
26 78 48
26 79 49
26 95 21
26 97 78
27 28 47
27 35 39
27 40 14
27 48 14
27 68 25
27 69 88
27 71 16
27 85 88
27 94 80
28 30 68
28 36 73
28 40 10
28 58 70
28 69 41
28 70 75
28 74 13
28 78 46
28 81 22
28 82 31
28 83 55
28 90 57
28 96 70
28 99 84
29 32 78
29 36 76
29 37 85
29 39 37
29 45 56
29 47 12
29 57 48
29 62 72
29 66 19
29 69 35
29 71 36
29 73 23
29 77 79
29 81 33
29 82 84
29 83 46
29 89 59
30 31 10
30 44 18
30 49 88
30 50 78
30 59 13
30 73 33
30 74 33
30 82 44
30 90 50
30 96 80
30 99 15
31 32 73
31 33 35
31 36 78
31 46 77
31 52 64
31 58 10
31 60 83
31 66 61
31 73 88
31 85 34
31 86 87
31 93 72
31 96 41
32 39 41
32 41 62
32 44 40
32 45 10
32 62 60
32 74 13
32 75 68
32 86 68
32 90 35
32 91 27
32 92 83
32 97 30
33 36 17
33 42 32
33 53 12
33 57 16
33 59 32
33 73 43
33 79 87
33 84 22
33 93 75
34 35 81
34 36 66
34 37 18
34 57 51
34 58 51
34 65 69
34 72 83
34 74 47
34 83 54
34 92 46
35 38 79
35 39 26
35 46 13
35 49 28
35 52 50
35 53 37
35 52 85
35 53 35
35 67 34
35 79 74
35 82 37
35 83 57
35 84 73
35 95 84
35 96 51
36 42 55
36 43 27
36 62 49
36 64 87
36 69 53
36 70 39
36 74 68
36 82 83
36 83 70
36 93 50
37 50 82
37 81 59
37 86 72
38 42 16
38 45 66
38 57 50
38 65 16
38 72 88
38 86 73
38 87 58
39 42 25
39 43 10
39 48 45
39 50 21
39 62 38
39 65 56
39 66 42
39 75 47
39 82 65
39 84 58
39 85 64
39 87 50
39 88 22
39 89 15
39 98 15
40 45 67
40 55 34
40 60 84
40 69 57
40 75 86
40 82 23
40 86 10
40 97 62
41 45 36
41 52 32
41 56 55
41 57 35
41 58 60
41 66 73
41 72 69
41 73 41
41 88 20
41 89 41
41 93 24
42 51 36
42 55 26
42 57 39
42 63 19
42 64 46
42 74 68
42 76 35
42 95 56
42 100 32
43 57 87
43 79 62
43 80 70
43 85 19
43 98 27
44 45 37
44 48 49
44 53 60
44 59 34
44 60 65
44 87 67
44 94 17
45 55 35
45 58 21
45 74 18
45 85 40
46 50 57
46 55 20
46 59 83
46 60 54
46 61 76
46 62 14
46 64 77
46 73 81
46 74 87
46 80 84
46 81 68
47 58 17
47 60 38
47 73 82
47 80 61
47 82 15
47 86 63
47 89 77
47 90 14
47 91 38
47 95 19
47 96 89
47 97 77
47 98 47
48 49 31
48 50 14
48 64 52
48 65 69
48 79 49
48 80 86
48 87 81
48 91 52
49 52 43
49 68 11
49 69 38
49 88 54
49 94 58
49 97 62
49 100 12
50 57 66
50 59 50
50 60 12
50 61 50
50 68 14
50 73 76
50 79 84
50 80 18
50 81 25
50 87 11
50 95 23
51 59 39
51 63 50
51 78 37
51 81 51
51 83 43
51 95 62
51 97 64
52 59 64
52 64 54
52 67 73
52 73 64
52 79 14
52 92 57
52 95 63
53 66 49
53 75 18
53 76 36
53 85 24
53 87 53
53 88 67
53 92 56
54 66 42
54 73 46
54 75 45
54 80 62
54 84 10
54 87 43
54 96 10
55 72 56
55 74 60
55 92 27
55 95 85
55 98 52
56 64 57
56 70 76
56 71 23
56 74 65
56 79 56
56 80 76
56 90 39
56 92 56
57 75 52
57 78 14
57 79 65
57 88 82
57 97 69
57 98 78
57 100 72
58 72 88
58 76 47
58 77 10
58 79 34
58 85 78
58 90 66
58 91 42
58 95 61
58 97 23
59 63 26
59 72 74
59 82 12
59 83 81
59 84 34
59 85 86
59 86 23
59 87 42
59 96 56
59 99 25
60 61 15
60 62 56
60 70 36
60 75 62
60 98 28
60 99 10
61 66 22
61 76 70
61 79 82
61 83 63
62 77 44
62 78 77
62 87 16
62 90 86
62 94 55
63 69 71
63 71 30
63 75 40
63 90 75
63 99 25
64 84 85
64 89 87
64 96 20
64 98 40
65 66 80
65 67 40
65 68 35
65 79 75
66 67 10
66 74 10
66 86 32
66 96 69
66 99 27
67 75 12
67 83 36
67 87 53
67 88 11
68 71 71
68 79 63
68 81 31
68 93 88
68 95 49
69 78 48
69 82 32
69 84 88
69 87 22
69 97 23
69 99 28
70 71 89
70 74 23
70 75 11
70 88 69
70 93 51
70 96 57
71 73 24
71 92 64
71 97 88
71 98 62
72 79 29
72 86 11
73 76 56
73 78 73
74 76 60
74 80 34
74 98 40
75 85 26
75 88 13
76 96 41
76 98 76
76 100 24
77 80 75
77 91 24
77 92 31
77 96 20
77 98 32
78 86 37
78 91 64
78 96 60
79 80 21
79 81 27
79 89 48
79 90 38
79 94 34
79 99 22
80 84 86
80 88 28
81 85 47
81 89 65
81 93 83
81 97 87
82 84 71
83 85 64
83 88 77
84 86 46
84 93 49
84 98 16
84 99 11
85 86 17
85 88 25
86 94 47
86 98 65
87 90 10
87 91 55
87 92 79
87 96 87
87 98 72
88 89 32
88 94 65
88 95 83
88 97 12
88 98 61
89 91 23
90 94 82
90 96 14
91 97 67
92 93 25
92 98 13
92 99 21
92 100 30
93 94 38
93 97 68
94 98 58
95 98 55
95 100 13
96 98 38
97 100 45
99 100 37
10 90 999
0 0
Output:
Scenario #1
Minimum Number of Trips = 5

Scenario #2
Minimum Number of Trips = 8

Scenario #3
Minimum Number of Trips = 5

Scenario #4
Minimum Number of Trips = 3

Scenario #5
Minimum Number of Trips = 28

Scenario #6
Minimum Number of Trips = 13