15 15 40
1 2 1
2 1 1
1 3 1
3 1 1
2 4 1
4 2 1
2 5 1
5 2 1
3 4 1
4 3 1
3 5 1
5 3 1
4 6 1
6 4 1
5 6 1
6 5 1
6 7 1
7 6 1
6 8 1
8 6 1
7 9 1
9 7 1
8 9 1
9 8 1
9 10 1
10 9 1
9 11 1
11 9 1
10 12 1
12 10 1
11 12 1
12 11 1
12 13 1
13 12 1
12 14 1
14 12 1
13 15 1
15 13 1
14 15 1
15 14 1