Bài đồ thị siêu cơ bản nên đề bài vô cùng ngắn gọn:

Quân có một đồ thị đầy đủ, vô hướng, có trọng số gồm ~n~ đỉnh. Trọng số của đỉnh thứ ~i~ là ~a_i~. Trọng số của cạnh nối giữa đỉnh ~u~ và đỉnh ~v~ là ~\frac{a_u + a_v}{gcd(a_u, a_v)}~. Cảm giác bài chưa đủ khó nên Quân vẽ thêm ~m~ cạnh nối nữa. Cạnh thứ ~i~ nối giữa hai đỉnh ~u_i~ và ~v_i~, và có trọng số là ~w_i~.

Hãy tính độ dài đường đi ngắn nhất từ đỉnh ~1~ tới mỗi đỉnh còn lại.

Input

• Dòng đầu chứa hai số nguyên không âm ~n, m~ ~(1 \le n \le 10^5, 0 \le m \le 10^4)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^5)~.
• ~m~ dòng cuối cùng, dòng thứ ~i~ chứa ba số nguyên dương ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le n, 1 \le w_i \le 10^5)~.

Output

• In ra ~n~ số nguyên không âm, số thứ ~i~ là độ dài đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~i~.

Subtask

• Subtask ~1~ (~20\%~ số điểm): ~n \le 1000~
• Subtask ~2~ (~20\%~ số điểm): Dãy ~a~ đôi một giống nhau
• Subtask ~3~ (~20\%~ số điểm): ~m = 0; \ a_i \le 50 \ \forall i \in [1, n]~
• Subtask ~4~ (~20\%~ số điểm): ~m = 0~
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm

Sample input 1

3 1
1 2 3
2 3 1

Sample output 1

0 3 4