18 16
0 1 1
0 2 1
3 4 1
3 5 1
6 9 10
7 10 30
8 11 90
8 9 1
7 9 1
12 15 270
13 16 900
14 17 1000
14 17 1000
14 17 700
13 15 1
14 15 1