Sau những ngày tính toán các phương án, không khí trong căn cứ dường như sục sôi hơn bao giờ hết. Những mệnh lệnh quan trọng được soạn thảo, từng chỉ thị được ghi lại bằng chữ viết nắn nót trên giấy dó. Mọi người hiểu rằng, khi thời cơ đến, tin tức phải truyền đi nhanh chóng, đồng loạt. Sự chậm trễ, dù chỉ một ngày, cũng có thể làm lỡ nhịp tổng khởi nghĩa.

Lúc này, chúng ta lại có một nhiệm vụ mới, đó là truyền tải thông tin đến tiền tuyến một cách sớm nhất. Gói tài liệu được bọc trong tấm vải nâu, niêm phong bằng sáp đỏ, giản dị nhưng thiêng liêng. Khi cầm nó trong tay, Phong thấy nhịp tim mình như gắn với từng con chữ bên trong. Đó không chỉ là giấy, mà là mệnh lệnh của lịch sử, là nhịp cầu nối liền khát vọng của hàng triệu con người.

Lục lọi trong kí ức của mình, Phong biết rằng con đường đưa tin đầy gian nan. Các chiến sĩ giao liên len lỏi qua những lối mòn trong rừng. Đêm đến, họ lội qua suối lạnh, men theo sườn núi tối đen như mực. Có lúc, ánh đèn pin từ đồn lính loang loáng chiếu gần sát, buộc họ phải ép mình xuống bãi cỏ ướt sũng. Tiếng giày đinh dồn dập, tiếng quát tháo thô bạo vọng ra khiến tim những người lính đập thình thịch. Nhưng rồi, tất cả qua đi, để lại sau lưng một khoảng tĩnh mịch nặng nề.

Có một lần, Phong cũng lên đường đi làm giao liên. Trên đường đi, Phong nhận ra rằng công việc truyền tin không hề đơn giản. Nó đòi hỏi sự kiên nhẫn, ý chí và cả sự hy sinh thầm lặng. Không ai tung hô những người đưa tin, nhưng nếu thiếu họ, không một chỉ thị nào có thể đến đúng nơi, đúng lúc. Trong khoảnh khắc, Phong thấm thía rằng cách mạng không chỉ được làm nên bởi những tiếng hô vang nơi quảng trường, mà còn bởi từng bước chân lặng lẽ trong đêm tối.

Khi bình minh vừa ló rạng, sau một đêm dài vượt rừng, Phong và đồng đội đến một lán trại nhỏ nằm giữa thung lũng. Nơi đây là điểm tập kết của tiền tuyến. Những gương mặt mệt mỏi nhưng ánh mắt sáng ngời nhìn họ bước vào. Người chỉ huy tiếp nhận gói tài liệu, mở niêm phong, đọc lướt qua những dòng chữ rồi khẽ gật đầu. Không cần nhiều lời, ông nắm chặt tay Phong, ánh mắt rực sáng như ngọn lửa: đó là lời cảm ơn sâu sắc nhất.

Trong lán, bầu không khí bỗng như thay đổi. Những người chiến sĩ trẻ lập tức lấy giấy bút, sao chép chỉ thị, chuẩn bị gửi đi khắp các vùng. Họ biết rằng, mỗi tờ giấy nhỏ này khi đến tay nhân dân sẽ biến thành cờ đỏ, thành khẩu hiệu, thành dòng người xuống đường.

Ngồi trong góc lán, Phong lặng im quan sát. Anh thấy rõ một sự thật: chiến thắng của cách mạng được dệt nên từ những sợi dây liên lạc mong manh nhưng kiên cường. Giữa núi rừng, những gói tài liệu bọc vải nâu trở thành dòng máu chảy xuyên suốt cơ thể dân tộc, nối liền ý chí của lãnh đạo với sức mạnh quần chúng.

Khi trở về căn cứ trong rừng, Phong nhận thấy việc truyền tin thế này là quá chậm và chưa hiệu quả. Phong tính toán được rằng, đến lúc diễn ra chiến đấu thật, mệnh lệnh phải được truyền đi trong không quá ~L~ đơn vị thời gian. Hiện tại, từ căn cứ đến tiền tuyến có thể chia thành ~N~ điểm, trong đó căn cứ là điểm ~S~, còn tiền tuyến là điểm ~T~. Có ~M~ con đường 2 chiều, con đường thứ ~i~ được mô tả bởi 3 số ~u_i, v_i, w_i~, cho biết từ điểm có thể di chuyển qua lại giữa 2 điểm ~u_i~ và ~v_i~ và mất ~w_i~ đơn vị thời gian.

Nhưng may mắn là trước đó, mỗi điểm đã được gán một mã liên lạc ~c_i~. Những điểm có cùng mã liên lạc có thể truyền tin ngay lập tức cho nhau mà không tốn thời gian. Sắp tới, có ~Q~ đợt chi viện, được diễn ra lần lượt từ đợt thứ nhất tới đợt thứ ~Q~, đợt thứ ~j~ sẽ đẩy lùi một số quân địch, cho phép quân ta có thêm phương án liên lạc hai chiều từ điểm có mã liên lạc ~x_j~ đến điểm có mã liên lạc ~y_j~ trong ~z_j~ đơn vị thời gian.

Nhiệm vụ của bạn và Phong bây giờ là tính xem sau bao nhiêu đợt chi viện thì ta có thể truyền tin từ điểm ~S~ tới ~T~ trong không quá ~L~ đơn vị thời gian.

Nếu sau ~Q~ đợt chi viện mà ta không thể truyền tin trong ~L~ đơn vị thời gian, hãy in ra ~-1~ để ban chỉ huy huy động thêm viện trợ.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~N~, ~M~ và ~K~ ~(2 \leq K \leq N \leq 10^5~ và ~1 \leq M \leq 10^5)~ lần lượt là số lượng cứ điểm, số con đường ~2~ chiều và số mã liên lạc.

• Dòng thứ hai chứa ~N~ số nguyên ~c_1, c_2, c_3, \cdots c_n~ (~1 \leq c_i \leq K~), trong đó ~c_i~ cho biết mã liêc lạc của cứ điểm ~i~.

• Trong ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên dương ~u_i~, ~v_i~ và ~w_i~ ~(1 \leq u_i, v_i \leq N, u_i \neq v_i~ và ~1 \leq w_i \leq 10^9)~, cho biết có thể đi lại giữa ~2~ cứ điểm ~u_i~ và ~v_i~, tốn ~w_i~ đơn vị thời gian.

• Dòng tiếp theo chứa ~4~ số nguyên dương ~Q, L, S, T~ (~1 \leq Q \leq 10^5~, ~1 \leq L \leq 10^{14}~, ~1 \leq S, T \leq N~) lần lượt là số đợt chi viện, số đơn vị thời gian không được vượt quá, vị trí của căn cứ điểm và vị trí của tiền tuyến.

• Trong ~Q~ dòng tiếp theo, dòng thứ ~j~ chứa ~3~ số nguyên dương ~x_j, y_j~ và ~z_j~ (~1 \leq x_j, y_j \leq N~, ~x_j \neq y_j~ và ~1 \leq z_j \leq 10^9~), có ý nghĩa là ~1~ đợt chi viện giúp quân của ta giúp ta liên kết một vùng có mã liên lạc ~x_j~ với một vùng có mã liên lạc ~y_j~ và di chuyển trong ~z_j~ đơn vị thời gian.

Output

• Nếu không thể di chuyển từ ~S~ đến ~T~ với thời gian không quá ~L~ sau ~Q~ đợt chi viện, in ra ~-1~. Ngược lại, in ra số đợt chi viện tối thiểu để ta có thể di chuyển từ ~S~ đến ~T~ với thời gian không quá ~L~.

Scoring

Sample Input 1

4 3 3
1 3 2 2
1 3 5
2 4 5
1 2 10
3 2 1 4
1 2 5
1 3 1
3 2 1

Sample Output 1

3