24 s   128 MB

## Description

### Sample Output

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

17
6
-1


## Source

2013 ACPC (Arab Collegiate Programming Contest)