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 (~1000~ms ~=~ ~1~s) đượ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_{i} \times C_{j} \times T~ 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. ~M \leq 400000~

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

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} \leq B_{i} \leq N)~

Output

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

Sample Input

60000 3
1 3 3
3 4 1
2 5 2

Sample Output

19

Note

Độ 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~.