8 4
1 2 3 4 5 6 7 8
0 1 10 1
1 2 10 1
0 3 10 1
0 4 10 0
0 5 10 1
5 6 10 0
6 7 10 1
0 6 10 5
1 4 100000 2 2
0 7 100000 3
0 0 100000 0