Trong một tương lai xa xôi, có một đế chế vũ trụ rộng lớn với vô số hành tinh. Những hành tinh này đều có cổng dịch chuyển không gian, cho phép người dân di chuyển từ hành tinh này sang hành tinh khác. Mỗi hành tinh có một "năng lượng cốt lõi" và giữa các cặp hành tinh có thể di chuyển qua lại với nhau bằng các cổng dịch chuyển, đồng thời, khi sử dụng cổng sẽ mất một lượng thời gian phụ thuộc vào năng lượng cốt lõi của hai hành tinh tương ứng.

Trong quá khứ khi sử dụng cổng dịch chuyển giữa hai hành tinh sẽ mất khoảng thời gian bằng tổng độ lớn năng lượng cốt lõi của cả hai hành tinh. Tuy nhiên, với sự xuất hiện trong những năm gần đây của một kỹ sư thiên tài với đầy tham vọng Tyzhu, anh ấy đã tìm ra cách để giảm thiểu thời gian dịch chuyển ấy. Hiện tại, thời gian dịch chuyển giữa hai hành tinh bất kì sẽ giảm đi ~x~ lần với ~x~ lớn nhất sao cho lượng năng lượng của hành tinh thứ nhất và hành tinh thứ hai có thể lần lượt được biểu diễn thành ~x \times k~ và ~x \times z~ (~x, k, z~ là các số nguyên dương).

Thế nhưng, do có nhiều phản hồi tiêu cực từ cư dân các cư dân và nhà khoa học từ các hành tinh về vấn đề thời gian dịch chuyển của các cánh cổng chưa tối ưu, nên Tyzhu phải tìm cách nâng cấp hệ thống càng sớm càng tốt. Vốn dĩ, việc tìm ra cách để cải thiện hệ thống không hề dễ dàng và tốn rất nhiều thời gian nên một số tuyến đường hai chiều di chuyển bằng tàu vũ trụ giữa hai hành tinh bất kì đã được bổ sung vào và sẽ mất một lượng thời gian nhất định. Việc lập ra các tuyến đường này không những giúp chữa cháy vấn đề hiện tại mà còn nhằm mục đích khảo sát thời gian di chuyển từ hành tinh trung tâm đến các hành tinh khác trong vũ trụ (hành tinh thứ nhất hiện tại đang là trung tâm của vũ trụ).

Do công việc chồng chất nên Tyzhu không có đủ thời gian để tính toán thời gian tối thiểu cho việc di chuyển từ hành tinh trung tâm đến các hành tinh còn lại bằng việc sử dụng các cổng dịch chuyển và các tuyến đưởng bổ sung. Bạn hãy giúp anh ấy giải quyết vấn đề này nhé!

Dữ liệu

Nhập từ file newuniverse.inp:

• Dòng đầu chứa hai số nguyên ~n, m~ ~(1 \le n \le 10^5, 0 \le m \le 10^5)~ lần lượt là số hành tinh hiện tại và số tuyến đường bổ sung.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a~ ~(a_i \le 10^5)~ mô tả mức năng lượng của ~n~ hành tinh.
• ~m~ dòng tiếp theo mỗi dòng chứa ~3~ số nguyên ~u, v, c~ mô tả tuyến đường bổ sung ~(1 \le u,v \le n,1 \le c \le 10^5)~.

Kết quả

Ghi ra file newuniverse.out:

• In ra ~n~ số nguyên, số nguyên thứ ~i~ thể hiện thời gian tối thiểu để đi từ hành tinh trung tâm đến hành tinh thứ ~i~.

Giới hạn

• ~20\%~ số điểm ứng với ~n \lt 1000~.
• ~20\%~ số điểm có ~a_i = a_{i+1} \ \forall i \in [1,n-1]~.
• ~20\%~ số điểm có ~m = 0, a_i \le 50~.
• ~20\%~ số điểm có ~m = 0~.
• ~20\%~ số điểm còn lại không có ràng buộc gì thêm.

Ví dụ

Dữ liệu

3 1
1 2 3
2 3 1

Kết quả

0 3 4