5 15 15
1 3 622809
1 5 229876
5 2 442313
2 5 727278
1 4 977609
4 2 227894
3 5 903365
3 4 68582
4 1 72258
3 2 335607
4 5 140864
3 1 469688
1 2 161242
4 3 12301
2 3 52120
5 1
2 3
4 1
3 4
2 1
1 2
5 2
5 3
1 5
4 2
3 2
3 1
1 4
3 5
4 3