input:

13
3 4
1 2 4
2 1 3
2 3 2
3 1 1
10 12
1 2 1
2 3 1
3 4 1
4 1 1
4 5 1
5 6 1
6 7 1
7 4 1
3 8 1
8 9 1
9 10 1
10 3 1
2 1
1 2 1
12 20
1 2 3
2 1 3
1 3 2
3 2 1
1 4 1
4 5 1
5 2 1
1 6 1
6 2 2
1 7 1
7 2 2
1 8 1
8 2 2
1 9 1
9 2 2
2 10 1
10 1 2
2 11 1
11 12 1
12 1 1
500 249500
1 2 1
1 3 2
1 4 3
1 5 4
1 6 5
1 7 6
...

output:

7 2
4 3
-1 -1
6 21
500 616118143
1002500000 124750
566 124750
2 124750
-1 -1
500098704 2
8500 207839182
116655401 5046
500000000000 1

result:

ok 13 lines