Các bé trường mầm non SuperKids tham quan một khu du lịch sinh thái. Bản đồ khu vực này gồm \(n\) địa điểm đánh số từ \(1\) tới \(n\) và \(m\) con đường hai chiều đánh số từ \(1\) tới \(m\), con đường thứ \(i\) nối giữa hai địa điểm \(u_i\) và \(v_i\) và để đi hết con đường này mất thời gian \(w_i\), hệ thống giao thông đảm bảo sự đi lại giữa hai địa điểm bất kỳ.

Sau một ngày dài vui chơi, các bé phân tán ra nhiều địa điểm trong khu du lịch, cụ thể là có \(c_i\) bé ở tại địa điểm \(i\). Tới giờ về, Ban tổ chức muốn tập hợp các bé tại địa điểm \(1\) và để tránh đi lạc, hành trình của các bé trở về địa điểm \(1\) được quy định từ trước: Mỗi bé sẽ đi theo đường đi ngắn nhất để trở về địa điểm \(1\), nếu có nhiều đường đi cùng là ngắn nhất, bé sẽ chọn đường đi có thứ tự từ điển nhỏ nhất.

Để việc tập hợp đỡ vất vả hơn, Ban tổ chức bố trí thêm một trạm xe tại một địa điểm \(x\) nào đó. Các bé đi theo hành trình đã quy định, nếu hành trình đó có đi qua địa điểm \(x\) thì khi tới \(x\), bé có hai sự lựa chọn tùy theo cách nào đi nhanh hơn:

• Hoặc lên xe đi thẳng về địa điểm \(1\) mất thời gian là \(T\).
• Hoặc tiếp tục đi bộ về địa điểm \(1\) theo hành trình cũ

Hãy giúp ban tổ chức tìm vị trí đặt trạm xe (địa điểm \(x\)) sao cho tổng thời gian đi của các bé giảm được nhiều nhất.

Input

• Dòng \(1\) chứa hai số nguyên dương \(n \leq 10^5; m \leq 2\cdot10^5; T \leq 10^9\)
• Dòng \(2\) chứa \(n\) số nguyên \(c_1, c_2, ..., c_n\) (\(\forall i: 0 \leq c_i \leq 10^4\))
• \(m\) dòng tiếp theo, dòng thứ \(i\) ghi ba số nguyên dương \(u_i, v_i, w_i\) (\(\forall i: w_i \leq 10^9\))
• Các số trên một dòng của input file được ghi cách nhau bởi dấu cách. Thời gian đi bộ từ mỗi địa điểm về địa điểm \(1\) theo con đường nhanh nhất không vượt quá \(10^9\)

Output

• Ghi ra một số nguyên duy nhất là lượng thời gian giảm đi tính trên tổng thời gian di chuyển của tất cả các bé theo phương án đặt trạm xe tìm được.

Example

5 6 2
1 2 3 4 5
1 2 2
1 3 3
2 4 3
3 4 5
4 5 2
3 5 7

27