9 5 1 9
12
1 2 1
1 3 1
1 4 1
4 5 1
3 5 1
2 5 1
5 6 1
5 7 1
5 8 1
8 9 1
7 9 1
6 9 1