/*
^^^^TEST^^^^
9
1 1 99
2 1 100
1 2 1
2 2 2
9 1 1000
0 0  0
----
1202
$$$TEST$$$

^^^^TEST^^^^
9
1 9 1000
2 8 1000
7 7 100
0 0  0
----
2000
$$$TEST$$$

^^^^TEST^^^^
9
1 1 99
2 1 100
1 2 1
2 2 2
1 9 1000
2 8 1000
7 7 100
0 0  0
----
2202
$$$TEST$$$


^^^TEST^^^
8
2 3 13
2 6  6
3 5  7
4 4 14
5 2 21
5 6  4
6 3 15
7 2 14
0 0  0
-----
67
$$$TEST$$$

*/