Tham quan

Nhân dịp nghỉ hè, John được các bạn cùng học đại học tới thăm và anh ta muốn thực hiện một chuyến đi dã ngoại dạo quanh thành phố. Qua đó anh ta muốn giới thiệu với bạn bè về thành phố mà anh ta đang sống.

Thành phố nơi John sống gồm \(n\) khu phố được liên kết với nhau bằng \(m\) con đường hai chiều. Con đường thứ \(i\) nối khu phố \(u_i\) với khu phố \(v_i\) và mất chi phí là \(w_i\) để đi qua. Từ khu phố này luôn có thể tới khu phố khác thông qua các con đường.

Khu phố thứ \(i\) sẽ có một chỉ số \(a_i\), nếu:

• \(a_i = 0\) thì khu phố này không có trạm dịch chuyển.

• \(a_i > 0\) thì khu phố này có một trạm dịch chuyển có thể dịch chuyển tới bất cứ một khu phố nào khác mà tại đó cũng có trạm dịch chuyển. Dịch chuyển tới khu phố \(u\) (\(a_u > 0\)) sẽ mất thời gian là \((a_i + a_u)^k\) với \(k\) là hằng số cho trước (\(1 \le k \le 2\)).

Theo lộ trình, vì không muốn mất thời gian nhiều, John xuất phát cùng các bạn ở khu phố \(1\) và muốn quay về tại khu phố \(n\) càng sớm càng tốt. Khi đi qua mỗi khu phố, John có thể chọn đi tiếp qua khu phố khác bằng các con đường hoặc sử dụng trạm dịch chuyển (nếu có).

Yêu cầu: Hãy giúp John tìm được đường đi tốn chi phí nhỏ nhất để trở về khu phố \(n\) và cho biết chi phí đó là bao nhiêu.

Input

Dữ liệu vào gồm

• Dòng thứ nhất gồm ba số nguyên dương \(n, m\) và \(k\) (\(3 \le n, m \le 2 \times 10^5\), \(1 \le k \le 2\));

• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le 2 \times 10^5\));

• Trên \(m\) dòng tiếp theo, dòng thứ \(i\) gồm ba số nguyên dương \(u_i, v_i\) và \(w_i\) --- có đường đi hai chiều từ khu phố \(u_i\) tới khu phố \(v_i\) (\(1 \le u_i, v_i \le n\), \(1 \le w_i \le 10^6\)).

Ràng buộc:

• Subtask 1: Có \(20\%\) số test tương ứng \(20\%\) điểm với \(a_i = 0\) với mọi \(1 \le i \le n\);

• Subtask 2: Có \(20\%\) số test tương ứng \(20\%\) điểm với \(k = 1\) và \(n \le 1000\);

• Subtask 3: Có \(10\%\) số test tương ứng \(10\%\) điểm với \(k = 1\) và có nhiều nhất \(100\) vị trí \(i\) mà \(a_i > 0\);

• Subtask 4: Có \(20\%\) số test tương ứng \(20\%\) điểm với \(k = 1\);

• Subtask 5: Có \(10\%\) số test tương ứng \(10\%\) điểm với \(k = 2\) và có nhiều nhất \(100\) vị trí \(i\) mà \(a_i > 0\);

• Subtask 6: Có \(20\%\) số test tương ứng \(20\%\) điểm với \(k = 2\).

Output

In ra một số duy nhất là kết quả của bài toán.

Example 1

Input:

5 5 1
0 0 0 1 2
1 2 4
1 3 7
2 4 5
4 3 4
2 5 10

Output:

12

Example 2

Input:

5 5 2
0 1 0 0 2
1 2 4
1 3 7
2 4 5
4 3 4
2 5 10

Output:

13

Note

Ví dụ 1 (\(k = 1\)): đường đi tối ưu là \(1 \to 2 \to 4\) rồi dịch chuyển tới \(5\). Tổng chi phí là \(4 + 5 + (1 + 2)^1 = 12\).

Ví dụ 2 (\(k = 2\)): đường đi tối ưu là \(1 \to 2\) rồi dịch chuyển tới \(5\). Tổng chi phí là \(4 + (1 + 2)^2 = 13\).