6 2 5
6
1 2 1
2 3 1
3 4 1
3 5 100
4 5 1
5 6 1
6
1 2 1
2 3 1
3 4 1
3 5 1
4 5 100
5 6 1