Phát biểu bài toán

Thành phố Hội An có ~ N ~ khu phố được đánh số từ ~ 1 ~ đến ~ N ~, được nối với nhau bởi ~ M ~ con đường hai chiều, mỗi con đường có độ dài riêng biệt. Bill Aka muốn đi từ khu phố ~ 1 ~ (rìa thành phố) đến khu phố ~ N ~ (trung tâm thành phố) với:

1. Độ dài đường đi là ngắn nhất.
2. Tổng số chậu hoa được trưng bày dọc đường đi là nhiều nhất (trên các khu phố mà đường đi đi qua).

Nếu không có đường đi nào từ khu phố ~ 1 ~ đến khu phố ~ N ~, in ra impossible. Ngược lại, in ra độ dài đường đi ngắn nhất và tổng số chậu hoa tối đa mà Aka có thể nhìn thấy.

Dữ liệu vào

1. Dòng đầu chứa số nguyên ~ N ~ (~ 1 \leq N \leq 10^5 ~): Số khu phố.
2. Dòng thứ hai chứa ~ N ~ số nguyên ~ P_1, P_2, \dots, P_N ~ (~ 0 \leq P_i \leq 10^9 ~): Số chậu hoa tại từng khu phố.
3. Dòng thứ ba chứa số nguyên ~ M ~ (~ 0 \leq M \leq 10^5 ~): Số con đường.
4. ~ M ~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~ U, V, C ~:
   • ~ U, V ~ (~ 1 \leq U, V \leq N ~): Hai khu phố được nối bởi con đường.
   • ~ C ~ (~ 1 \leq C \leq 10^9 ~): Chiều dài con đường.

Kết quả

• Nếu không tồn tại đường đi từ khu phố ~ 1 ~ đến khu phố ~ N ~: In ra impossible.
• Ngược lại: In ra hai số nguyên:
  1. Độ dài đường đi ngắn nhất.
  2. Tổng số chậu hoa tối đa mà Aka có thể nhìn thấy trên đường đi đó.

Ví dụ

Input

8
2 1 1 1 100 1 1 2
10
1 2 1
2 3 2
3 4 2
4 8 1
1 8 7
1 5 3
5 8 4
1 6 2
6 7 2
7 8 2

Output

6 7

Giải thích:

• Con đường tốt nhất là: ~ 1 \to 2 \to 3 \to 4 \to 8 ~.
  • Độ dài: ~ 1 + 2 + 2 + 1 = 6 ~.
  • Tổng số chậu hoa: ~ 2 + 1 + 1 + 1 + 2 = 7 ~.