Cây khung 2

Cho một đồ thị vô hướng có trọng số \(G\). Biết rằng, ban đầu tất cả các cạnh đều có trọng số bằng \(0\), có \(q\) thao tác thay đổi, mỗi thao tác mô tả bằng \(5\) số: \(i_{min},\ i_{max},\ j_{min},\ j_{max},\ w\), nghĩa là các cạnh \((i, j)\) mà \(i_{min} \le i \le i_{max} < j_{min} \le j \le j_{max}\) được thay đổi một lượng \(w\).

Yêu cầu: Tìm trọng số của cây khung nhỏ nhất của \(G\).

Input

• Dòng đầu chứa hai số nguyên \(n, q\).
• Tiếp theo là \(q\) dòng, mỗi dòng chứa \(5\) số \(i_{min},\ i_{max},\ j_{min},\ j_{max},\ w\ (1 \le i_{min} \le i_{max} < j_{min} \le j_{max} \le n; |w| \le 10^6)\).

Output

• Gồm một dòng chứa một số là trọng số cây khung nhỏ nhất của \(G\).

Example

3 2
1 1 3 3 3
1 2 3 3 -2

-2