input.txt


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

6 10 20
6 12 1 3
1 9 1 2
3 2 1 2
8 20 5 4
4 11 7 4
2 10 9 1
0 11 30
1 12 30
30 10 5 3
1 10 2
1 10 2 1
2 10 11
1 10 4 3
1 10 9 3
0 0 0