Hành Trình Người Sói

Remus Lupin trong hình dạng người sói, cần di chuyển từ khu vực $1$ đến khu vực $N$ trong Rừng Cấm. Rừng Cấm có $N$ khu vực được nối bởi $M$ con đường hai chiều.

Chu kỳ trăng có $T$ pha, đánh số từ $0$ đến $T-1$. Tại thời điểm $t$, pha trăng hiện tại là $tmodT$. Người sói bắt đầu tại khu vực $1$ ở thời điểm $0$ (pha $0$).

Mỗi con đường $i$ nối khu vực $u_i$ và $v_i$, có thời gian di chuyển $w_i$ đơn vị. Tuy nhiên, con đường chỉ an toàn khi pha trăng hiện tại nằm trong khoảng $[l_i,r_i]$. Nếu $l_i\le r_i$, đường an toàn tại các pha $l_i,l_i+1,\dots ,r_i$. Nếu $l_i>r_i$, khoảng quay vòng: đường an toàn tại các pha $l_i,l_i+1,\dots ,T-1,0,1,\dots ,r_i$.

Người sói chỉ có thể bắt đầu đi trên một con đường khi pha trăng hiện tại nằm trong khoảng an toàn. Khi đi trên đường $i$, thời gian tăng thêm $w_i$ và pha trăng khi đến nơi là $(t+w_i)modT$.

Tại bất kỳ khu vực nào, người sói có thể chờ đợi $1$ đơn vị thời gian (pha trăng tăng lên $1$).

Tìm thời gian ngắn nhất để di chuyển từ khu vực $1$ đến khu vực $N$. In $-1$ nếu không thể đến được.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $N$, $M$, $T$.
• $M$ dòng tiếp theo, mỗi dòng chứa năm số nguyên $u_i$, $v_i$, $w_i$, $l_i$, $r_i$ mô tả một con đường.

Dữ liệu ra

In một số nguyên duy nhất - thời gian ngắn nhất để đi từ khu vực $1$ đến khu vực $N$, hoặc $-1$ nếu không thể.

Ràng buộc

• $2\le N\le 5\times {10}^4$
• $1\le M\le {10}^5$
• $1\le T\le 100$
• $1\le w_i\le {10}^6$
• $0\le l_i,r_i<T$
• $1\le u_i,v_i\le N$, $u_i\ne v_i$

Ví dụ