5 30
1 3 1 13
1 3 2 50
1 4 2 80
0 3 4
0 1 2
0 3 5
1 5 3 75
0 4 5
1 4 5 18
0 4 3
0 4 5
1 3 5 34
1 5 1 27
0 4 1
0 1 2
1 3 4 33
0 5 3
0 5 4
0 3 5
0 1 5
0 4 3
0 5 4
0 3 1
0 4 3
0 5 1
0 3 1
0 1 2
0 4 3
0 1 4
0 2 4