Trong một đơn đồ thị vô hướng liên thông có trọng số, người ta muốn thiết lập quan hệ “đỉnh ~u~ là quan trọng đối với đỉnh ~v~” theo cách sau:

• Các đỉnh được đánh số ~1, 2, \dots, N~. Đỉnh ~i~ được gán độ ưu tiên ~p_i~.
• Với mỗi đỉnh ~u~, đỉnh ~v~ được gọi là quan trọng đối với ~u~ nếu mọi đỉnh ~w~ không xa ~u~ hơn ~v~ đều có độ ưu tiên không vượt quá ~p_v~. Tức là ~\forall w: dist(u, w) \le dist(u, v) \Rightarrow p_w \le p_v~.

Yêu cầu: Xác định số mối quan hệ “đỉnh ~v~ là quan trọng với đỉnh ~u~”.

Input

• Dòng 1: hai số nguyên ~N, M~ (~1 \le N \le 30000; 1 \le M \le 5N~) – số đỉnh, cạnh của đồ thị.
• Dòng 2: ~N~ số nguyên là ~p_1, p_2, \dots, p_N~ (~1 \le p_i \le 10~).
• Dòng 3 \dots M + 2: mỗi dòng ba số nguyên ~u, v, c~ chỉ một cạnh nối hai đỉnh ~u, v~ có trọng số ~c~ (~1 \le c \le 1000~).

Output

• Dòng 1: số nguyên kết quả.

Sample Input 1

4 3
2 3 1 1
1 4 3
2 3 2
3 4 2

Sample Output 1

9