100000 3
1 2 99998
2 2 99999
2 2 99999