3 3
0 1 1
1 2 2
2 0 3
4 5
0 1 1
1 2 2
2 3 3
3 1 4
0 2 0
3 1
0 1 1
6 7
0 1 0
1 2 2
2 3 4
3 4 6
4 5 8
5 0 10
1 4 12
10 9
0 1 1
2 3 3
4 5 5
6 7 7
8 9 9
0 2 11
0 4 12
0 6 13
0 8 14
10 45
0 1 1001
0 2 1002
0 3 1003
0 4 1004
0 5 1005
0 6 1006
0 7 1007
0 8 1008
0 9 1009
1 2 2002
1 3 2003
1 4 2004
1 5 2005
1 6 2006
1 7 2007
1 8 2008
1 9 2009
2 3 3003
2 4 3004
2 5 3005
2 6 3006
2 7 3007
2 8 3008
2 9 3009
3 4 4004
3 5 4005
3 6 4006
3 7 4007
3 8 4008
3 9 4009
4 5 5005
4 6 5006
4 7 5007
4 8 5008
4 9 5009
5 6 6006
5 7 6007
5 8 6008
5 9 6009
6 7 7007
6 8 7008
6 9 7009
7 8 8008
7 9 8009
8 9 9000
0 0