Trong một giấc mơ, NMinh thấy mình tham gia một đại tiệc Buffet khổng lồ. Bữa tiệc này có \(n\) căn phòng được nối bởi \(m\) hành lang, mỗi hành lang có một chiều rộng bất kỳ. Từ một căn phòng luôn luôn tồn tại đường đi đến một căn phòng khác bất kỳ. Tuy nhiên, đây không chỉ là một bữa tiệc bình thường mà là một đại tiệc Buffet hoành tráng. Mỗi căn phòng chứa số số lượng đồ ăn là \(c_i\). Và điều đặc biệt là, trong giấc mơ này, chiều rộng của cơ thể NMinh được xác định bở số lượng đồ ăn mà cậu tiêu thụ. Nếu có trở lên quá lớn, cậu sẽ trở nên quá béo và không thể di chuyển qua những hành lang hẹp hơn cơ thể hơn.

NMinh xuất phát từ căn phòng \(1\) và cậu ta muốn ăn tất cả các đồ ăn trong tất cả các phòng. Cậu muốn xác định rằng cơ thể ban đầu (lúc ở phòng \(1\) và chưa ăn đồ ăn ở đó) của cậu cần có chiều rộng nguyên dương lớn nhất là bao nhiêu để cậu có thể ăn hết đồ ăn ở tất cả các phòng. Lưu ý rằng cậu không cần chén đồ ăn ngay lần đầu cậu đến một căn phòng tuy nhiên thì mỗi lần đã ăn thì phải ăn cho hết đò ăn trong căn phòng đó nếu không cậu sẽ chủ tiệc phạt.

Input

• Dòng đầu chứa hai số nguyên dương \(n\), \(m\),\((1 \leq n \leq 10^5)\) \((n - 1 \leq m \leq 10^5)\).
• Dòng tiếp theo chứa n số nguyên dương \(c_i\) \((1 \leq c_i \leq 10^9)\).
• \(m\) dòng cuối cùng, mỗi dòng thứ chứa hai số nguyên dương \(u\), \(v\), \(w\) \((1 \leq u, v \leq n)\) \((1 ≤ w ≤ 10^9)\) cho biết có một hành lang nối giữa phòng \(u\) và phòng \(v\) và có chiều rộng \(w\).

Output

• Nếu việc ăn hết món ở tất cả các phòng là khả thi, in ra chiều rộng nguyên dương ban đầu lớn nhất có thể. Nếu không, in ra -1.

Example