Input
4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3
Output
17
12