Thăm bạn

Thành Nam đang có lễ rước đức Thánh Trần nhân dịp kỷ niệm ngày giỗ của ngài. Để đảm bảo an toàn giao thông, trên các tuyến phố mà đoàn rước đi qua, kể từ khi đoàn rước bắt đầu vào đầu phố cho đến khi đoàn rước đi qua hết phố, các phương tiện giao thông không được phép đi vào phố này (kể từ cả hai đầu phố). Tuy nhiên nếu có phương tiện nào đó đã ở trên phố trước khi đoàn rước đi vào phố thì nó vẫn di chuyển bình thường (kể từ cả hai đầu phố). Cũng trong khoảng thời gian đoàn rước đi trên các phố, Hùng muốn thăm một người bạn ở trong thành phố.

Thành Nam có thể được mô tả như là hệ thống giao thông gồm các tuyến phố với các điểm giao cắt là đầu mút của mỗi tuyến phố, giữa hai nút giao cắt có không quá một tuyến phố. Với mỗi tuyến phố, thời gian mà Hùng đi hết nó bằng với thời gian mà đoàn rước đi hết tuyến phố này.

Ví dụ: Nếu đoàn rước vào một tuyến phố nào đó ở thời điểm $10$ và cần $5$ đơn vị thời gian để đi hết tuyến phố thì Hùng chỉ có thể vào phố trước thời điểm $10$ hoặc từ thời điểm $15$ hay muộn hơn.

Đoàn rước xuất phát ở thời điểm $0$ tại điểm giao cắt đầu tiên trên hành trình và đi liên tục, không dừng lại, lần lượt qua các tuyến phố nối hai điểm giao cắt liên tiếp của hành trình. Hùng xuất phát từ $A$ ở thời điểm $H$, được phép dừng lại chờ ở bất kỳ điểm giao cắt nào trong bao lâu cũng được. Thời gian Hùng đi đến đích được tính từ lúc Hùng xuất phát (thời điểm $H$) đến lúc Hùng tới $B$.

Yêu cầu: Hãy xác định khoảng thời gian ít nhất Hùng có thể đi đến đích.

Dữ liệu vào

• Dòng đầu tiên ghi hai số nguyên dương $N,M$ ($2\le N\le 1000$, $2\le M\le 10000$) là số điểm giao cắt và số tuyến phố. Các điểm giao cắt được đánh số từ $1$ đến $N$.
• Dòng thứ hai chứa $4$ số nguyên $A,B,H,F$ với $A,B$ là vị trí xuất phát và đích đến của Hùng (dữ liệu đảm bảo có đường đi từ $A$ đến $B$), $H$ là chênh lệch thời gian giữa thời điểm xuất phát của đoàn rước và thời điểm xuất phát của Hùng (Hùng xuất phát sau $H$ đơn vị thời gian kể từ khi đoàn rước bắt đầu); $F$ là số lượng điểm giao cắt có trên hành trình của đoàn rước.
• Dòng thứ ba chứa $F$ số nguyên lần lượt là số hiệu các điểm giao cắt trên hành trình mà đoàn rước đi qua theo thứ tự. Hai điểm giao cắt liên tiếp trên hành trình luôn được nối bởi một tuyến phố. Dữ liệu đảm bảo rằng không có một tuyến phố nào mà đoàn rước đi qua nhiều hơn một lần.
• $M$ dòng cuối cùng, mỗi dòng ghi ba số nguyên $u,v$ và $t$ thể hiện có một tuyến phố hai chiều nối $u$ và $v$ ($u\ne v$) với thời gian đi hết nó (của Hùng cũng như của đoàn rước) là $t$. Giá trị của $t$ nằm trong khoảng $[1,1000]$.

Dữ liệu ra

Một số nguyên duy nhất là thời gian ngắn nhất mà Hùng có thể đi từ $A$ đến $B$.

Ràng buộc

• $2\le N\le 1000$, $2\le M\le 10000$.
• $1\le A,B\le N$, $A\ne B$, $0\le H\le {10}^6$, $1\le F\le M+1$.
• $1\le u,v\le N$, $u\ne v$, $1\le t\le 1000$; giữa hai điểm giao cắt có không quá một tuyến phố.

Subtasks

• $50\%$ số test có $N\le 50$ và $M\le 100$.

Ví dụ