배달 지연

Hannah는 최근 피자 굽기에 흥미를 느껴 스톡홀름 시내에 피자집을 열기로 했다. 여동생 Holly가 피자 배달을 맡았다. 두 사람의 피자집은 지역 주민들에게 큰 인기를 끌었지만, 안타깝게도 계속 적자를 보고 있다. Hannah는 피자집을 광고할 때 내건 보증 문구를 원인으로 본다.

맛있는 피자가 당기나요? 지금 바로 먹고 싶나요? Hannah의 피자집에서 주문하세요. 피자를 집 앞까지 배달해 드립니다. 주문한 시각부터 Hannah의 피자를 받을 때까지 20분이 넘게 걸리면 피자는 무료입니다!

Holly의 배달 차량은 피자를 원하는 만큼 실을 수 있지만, 쏟아지는 주문을 따라잡지 못해 늦은 배달로 여러 피자를 무료로 내주어야 했다.

Hannah는 스톡홀름의 도로와 교차로 지도를 준다. 또한 어제의 주문 목록도 준다. 주문 i는 시각 si에 교차로 ui에서 들어왔고, 이 주문의 피자는 시각 ti에 오븐에서 나와 배달 준비가 되었다. Hannah는 “선착순” 원칙을 엄격히 지킨다. 주문 i가 주문 j보다 먼저 들어왔다면(즉 si < sj), 주문 i의 피자가 주문 j의 피자보다 먼저 오븐에서 나오며(ti < tj), 주문 i의 피자는 주문 j의 피자보다 먼저 배달되어야 한다.

첫째 줄에 두 정수 n과 m이 주어진다(2 ≤ n ≤ 1 000, 1 ≤ m ≤ 5 000). n은 스톡홀름의 교차로 수, m은 도로 수다. 이어서 m개의 줄이 주어지며, i번째 줄에는 세 정수 ui, vi, di가 주어진다. 이는 교차로 ui와 vi 사이에 양방향 도로가 있고(1 ≤ ui, vi ≤ n, ui ≠ vi), Holly의 배달 차량이 이 도로를 어느 방향으로든 지나는 데 di 시간 단위가 걸린다는 뜻이다(0 ≤ di ≤ 10^8). 두 교차로 사이에는 도로가 최대 하나뿐이다.

다음 줄에는 주문 수 k가 주어진다(1 ≤ k ≤ 1 000). 이어서 k개의 줄이 주어지며, i번째 줄에는 세 정수 si, ui, ti가 주어진다. 이는 시각 si에 교차로 ui에서 주문이 들어왔고(2 ≤ ui ≤ n), 시각 ti에 배달 준비가 되었다는 뜻이다(0 ≤ si ≤ ti ≤ 10^8). 주문은 들어온 시각 순으로 주어지며, 1 ≤ i < j ≤ k인 모든 i, j에 대해 si < sj이고 ti < tj이다.

Hannah의 피자집은 교차로 1에 있고, Holly와 배달 차량은 시각 0에 피자집에 있다. 피자집에서 모든 교차로에 도달할 수 있다.

Holly가 이 값이 최소가 되는 배달 일정을 사용한다고 할 때, 고객이 주문한 시각부터 배달받을 때까지 기다리는 시간의 최댓값을 정수 하나로 출력한다.