Giải bài trực tuyến

Tuần vừa qua, diễn đàn Viet Guitar tổ chức buổi hòa nhạc thường niên với sự góp mặt của đông đảo thành viên từ khắp mọi nơi trên đất nước. Đây là một sự kiện đặc biệt không thể bỏ qua đối với Tuệ.

Dĩ nhiên tiết mục ấn tượng nhất của buổi hòa nhạc chính là bản hòa tấu guitar kéo dài N ms (1000ms = 1s) được trình diễn bởi tất cả M thành viên. Thành viên thứ i sẽ chơi đoạn nhạc của mình từ ms thứ A_i đến ms thứ B_i với cường độ là C_i. Độ hòa âm của 2 thành viên được tính bằng tích cường độ đoạn nhạc họ chơi nhân với quãng thời gian tính bằng số ms 2 người cùng chơi. Cụ thể hơn, độ hòa âm giữa 2 thành viên i, j bằng C_iC_jT với T là số ms chung mà 2 người cùng chơi.

Hãy giúp Tuệ tính tổng độ hòa âm của bản hòa tấu, được tính bằng tổng độ hòa âm của tất cả các cặp thành viên.

Input

Dòng 1: số N và số M
Dòng 2...M+1: dòng i+1 chứa 3 số A_i, B_i, C_i (A_i ≤ B_i ≤ N)

Output

Tổng độ hòa âm của bản hòa tấu

Constraints

M ≤ 400000

Tất cả các số trong input là số nguyên dương không vượt quá 10⁶.

Example

Input:
60000 3
1 3 3
3 4 1
2 5 2

Output:
19

Giải thích: độ hòa âm của các cặp thành viên (1-2), (1-3), (2-3) lần lượt là 3, 12, 4.