An đang làm việc trong một nhà máy và cần những cỗ máy đặc biệt để sản xuất linh kiện. Nhưng trước khi sử dụng, máy móc phải được lấy trong thành phố và giao cho nhà máy.

Bản đồ thành phố được biểu diễn như một đồ thị vô hướng có trọng số với ~n~ đỉnh và ~m~ cạnh, nhà máy nằm ở đỉnh số ~1~. Tại một số đỉnh có máy móc, máy thứ ~i~ được đặc trưng bởi một bộ ba số ~(v_i, h_i, t_i)~, trong đó ~v_i~ là đỉnh chứa máy, ~h_i~ là thời gian cần thiết để thiết lập và làm nóng máy, ~t_i~ là tốc độ sản xuất linh kiện.

Nhà máy có ~k~ người có thể đi lấy máy, mỗi người có thể lấy một máy. Nếu một người đã lấy một máy thì không thể đi lấy máy nữa. Như vậy, tổng cộng có thể lấy không quá ~k~ máy cho nhà máy.

Tất cả các người đi lấy máy sẽ xuất phát từ nhà máy và bắt đầu cùng một lúc tại thời điểm ~0~. Để đến được chiếc máy, người lấy máy cần dành thời gian bằng tổng trọng số của các con đường trên đường đi ngắn nhất dẫn đến đỉnh nơi đặt máy. Nếu máy ở đỉnh ~1~ thì không mất thời gian để lấy nó, nhưng dù sao thì cũng cần một người lấy máy.

Khi một chiếc máy đến nhà máy, đầu tiên nó cần ~h_i~ đơn vị thời gian để chuẩn bị, sau đó nó bắt đầu sản xuất liên tục một linh kiện trong ~t_i~ đơn vị thời gian. Bạn hãy giúp An tính thời gian tối thiểu để sản xuất ~V~ linh kiện là bao nhiêu?

Input

• Dòng đầu tiên chứa ba số nguyên ~n, m~ và ~k~ tương ứng là số đỉnh, số cạnh của đồ thị và số máy ~(2 \le n, m, k \le 2 \cdot 10^5)~.

• Dòng thứ ~i~ trong số ~m~ dòng tiếp theo chứa ba số nguyên ~a_i, b_i~ và ~c_i~, nghĩa là giữa các đỉnh ~a_i~ và ~b_i~ có một cạnh với trọng số ~c_i~ ~(1 \le a_i, b_i \le n; a_i \ne b_i; 1 \le c_i \le 10^9)~. Dữ liệu được đảm bảo rằng tất cả các cạnh là khác nhau.

• Dòng tiếp theo chứa một số nguyên ~s~ là số máy có trong thành phố ~(1 \le s \le 2 \cdot 10^5)~.

• Dòng thứ ~i~ trong số ~s~ dòng tiếp theo chứa mô tả về chiếc máy thứ ~i~, bao gồm ba số nguyên ~v_i, h_i~ và ~t_i~ tương ứng là đỉnh có máy, thời gian khởi động máy và thời gian sản xuất của một linh kiện ~(1 \le v_i \le n; 1 \le h_i, t_i \le 10^9)~.

• Dòng cuối cùng chứa một số nguyên ~V~ là số linh kiện cần được sản xuất ~(1 \le V \le 10^9)~.

Output

Ghi một số nguyên là thời gian tối thiểu để tạo ra ~V~ linh kiện.

Scoring

Sample Input 1

3 3 2
1 2 5
1 3 2
3 2 2
3
1 15 1
2 1 1
3 3 2
10

Sample Output 1

15

Sample Input 2

4 4 4
4 2 5
1 3 3
3 4 16
2 1 9
10
3 18 8
1 2 12
4 8 19
2 9 15
2 12 2
4 20 4
3 11 14
2 5 3
4 19 1
1 1 20
3

Sample Output 2

26