8 3
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
1 4 100000 2
0 7 100000