input:

2 4

1 1

1 1 2 100

2 1 2 50

1 1 2 60

5 1 1

output: 110