Nhân dịp khai trương cửa hàng bánh rán Doracake, cửa hàng có chương trình giao hàng miễn phí cho tất cả các đơn hàng giao đi. Do chỉ có một nhân viên giao hàng, chủ cửa hàng muốn biết với ~K~ đơn hàng cần giao được thống kê đến hiện tại, một khách hàng phải chờ nhiều nhất là bao lâu từ lúc đặt hàng đến lúc nhận hàng. Nhân viên sẽ giao hàng theo thứ tự đặt hàng, đảm bảo rằng đơn đặt trước phải được giao trước.

Thành phố có ~N~ địa điểm được đánh số từ ~1~ đến ~N~, cửa hàng được đặt tại địa điểm số ~1~. Các địa điểm được kết nối bằng ~M~ con đường hai chiều. Có tối đa một con đường nối hai địa điểm. Một địa điểm được đảm bảo có thể đến được từ bất kỳ địa điểm nào. Giả sử thời gian giao hàng tại các địa điểm và thời gian lấy bánh tại cửa hàng là không đáng kể. Vào thời điểm ~t = 0~ thì nhân viên giao hàng đã ở cửa hàng và sẵn sàng giao hàng.

Yêu cầu: Hãy viết chương trình cho biết thời gian khách hàng phải chờ nhiều nhất là bao lâu.

Input

Dòng đầu là hai số nguyên ~N, M~ ~(2 \le N \le 1000, 1 \le M \le 5000)~ lần lượt là số lượng địa điểm và số con đường trong thành phố. Dòng thứ ~i~ trong ~M~ dòng tiếp theo chứa ~3~ số nguyên ~u_i, v_i, d_i~ ~(1 \le u_i, v_i \le N; u_i \ne v_i; 0 \le d_i \le 10^8)~ cho biết con đường hai chiều nối hai địa điểm ~u_i~ và ~v_i~ cần thời gian ~d_i~ để giao hàng, thời gian này áp dụng cho cả hai chiều từ ~u_i~ đến ~v_i~ và từ ~v_i~ đến ~u_i~. Dòng tiếp theo chứa một số nguyên ~K~ ~(1 \le K \le 1000)~ cho biết số lượng đơn hàng. Dòng thứ ~j~ trong ~K~ dòng tiếp theo chứa ~3~ số nguyên ~s_j, u_j~ và ~t_j~ ~(2 \le u_j \le N, 0 \le s_j \le t_j \le 10^8)~ cho biết đơn hàng thứ ~j~ được đặt vào thời điểm ~s_j~ tại địa điểm ~u_j~ và bánh của đơn hàng này ra lò vào thời điểm ~t_j~. Đơn bánh thứ ~j~ chỉ được mang đi giao vào thời điểm lớn hơn hay bằng ~t_j~. Các đơn hàng được cho theo thứ tự thời điểm đặt tăng dần và đơn hàng đặt trước cũng sẽ có thời điểm bánh ra lò trước (nếu ~s_i < s_j~ thì ~t_i < t_j~).

Output

Một số nguyên là thời gian nhiều nhất khách hàng phải chờ.

Scoring

Sample Input 1

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

Sample Output 1

22

Notes

Thời điểm ~5~, nhân viên nhận bánh của đơn hàng ~1~ và ~2~ tại cửa hàng. Giao bánh cho đơn hàng ~1~ tại thời điểm ~12~, đơn hàng ~2~ tại thời điểm ~14~. Nhận bánh đơn hàng ~3~ tại thời điểm ~21~, giao bánh đơn hàng ~3~ tại thời điểm ~26~. Thời gian chờ lâu nhất ở đơn hàng ~3~ là ~22~.