Đoàn rước

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 đến khi đoàn rước đi qua hết tuyến phố, các phương tiện giao thông không được phép đi vào tuyến phố này. Tuy nhiên nếu có phương tiện nào đó đã ở trên tuyến phố trước khi đoàn rước đi vào tuyến phố đó thì nó vẫn di chuyển bình thường. Cũng trong khoảng thời gian đoàn rước đi trên các tuyến phố, An 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ố. Mỗi tuyến phố đi được theo cả hai chiều. Với mỗi tuyến phố, thời gian đi của An và đoàn rước là như nhau. An có thể dừng chờ tại các điểm giao cắt.

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ì An chỉ có thể vào tuyến phố trước thời điểm \(10\) hoặc từ thời điểm \(15\) trở đi.

Yêu cầu: Hãy xác định khoảng thời gian ít nhất An có thể đi đến đích (tính từ lúc An xuất phát).

Input

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 An (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 An (An 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ự. 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ố nối \(u\) và \(v\) với thời gian đi hết tuyến phố này là \(t\) (\(1 \le t \le 1000\)).
  Các số trên cùng một dòng được ghi cách nhau bởi dấu cách. Đoàn rước xuất phát tại điểm giao cắt đầu tiên của hành trình ở thời điểm \(0\) và đi liên tục không dừng.

Ràng buộc: Có \(40\%\) số test với \(2 \le n \le 100\), \(2 \le m \le 100\).

Output

In ra một số nguyên là thời gian ngắn nhất mà An có thể đi từ \(a\) đến \(b\).

Example

Input:

6 5
1 6 20 4
5 3 2 4
1 2 2
2 3 8
2 4 3
3 6 10
3 5 15

Output:

21

Note

Đoàn rước đi theo hành trình \(5 \to 3 \to 2 \to 4\): tuyến phố \((5,3)\) bị chiếm trong khoảng thời gian \([0, 15)\), tuyến phố \((3,2)\) trong \([15, 23)\) và tuyến phố \((2,4)\) trong \([23, 26)\).

An xuất phát tại điểm \(1\) ở thời điểm \(20\), đi theo \(1 \to 2 \to 3 \to 6\). Đến điểm \(2\) ở thời điểm \(22\), nhưng tuyến phố \((2,3)\) đang bị chiếm đến thời điểm \(23\) nên An phải đợi \(1\) đơn vị thời gian, rồi đi qua \((2,3)\) mất \(8\), đến điểm \(3\) ở thời điểm \(31\) và đi tiếp tuyến \((3,6)\) mất \(10\), đến đích ở thời điểm \(41\). Tổng thời gian là \(41 - 20 = 21\).