Suốt một tiếng đồng hồ, tôi giấu mình phía sau cửa sổ, [...] để lắng nghe trong chết lặng cuộc trò chuyện giữa Phúc và Miền, thấy tim mình tan ra từng phút một. Và không chỉ trái tim tôi, cả trái đất dường như cũng tan chảy trong khoảnh khắc đó. [...] Rõ ràng tình yêu của tôi đã đổ vỡ và tôi không thể vờ không nghe thấy những âm thanh loảng xoảng của nó, thậm chí tôi tưởng như mình có thể cảm nhận được những mảnh vỡ sắc nhọn kia đang làm rách tâm hồn tôi như thế nào. Tôi đã làm tất cả, chỉ vì tôi tin rằng tình yêu không thuần tuý là cảm xúc mà còn là một nỗ lực lớn lao để thu hẹp mọi khoảng cách, san bằng mọi hố sâu, cuối cùng để ai cũng có thể tìm thấy cho đời mình một chỗ nương náu đáng tin cậy. [...] Nhưng bây giờ thì tôi hiểu ra cuộc đời không giống như tôi nghĩ. Tôi hoàn toàn bị mất phương hướng khi biết rằng chỉ mười lăm tiếng đồng hồ nữa thôi, hạnh phúc sẽ lìa bỏ tôi vĩnh viễn...

(Ngày xưa có một chuyện tình – Nguyễn Nhật Ánh)

Biết Miền quyết định trở về với người cũ, Vinh đau khổ vô cùng. Anh không muốn níu kéo tình yêu trong vô vọng, bởi anh hiểu một khi người mình yêu đã quyết tâm ra đi, mọi sự níu kéo đều là vô ích. Quyết định buông tay trong đau đớn, anh đạp xe đi Đà Nẵng để Miền khỏi thấp thỏm khi bỏ nhà ra đi.

Mạng lưới giao thông từ nhà Vinh đi Đà Nẵng gồm ~N~ giao lộ được kết nối bởi ~M~ con đường hai chiều, độ dài các con đường có thể khác nhau. Các giao lộ được đánh số từ ~1~ tới ~N~, nhà Vinh nằm ở giao lộ ~1~, cửa ngõ thành phố Đà Nẵng nằm ở giao lộ ~N~. Mạng lưới giao thông đảm bảo tính thông suốt, nghĩa là giữa hai giao lộ bất kì luôn tồn tại một đường đi.

Đầu óc Vinh hoàn toàn trống rỗng. Anh bị mất phương hướng. Anh chỉ biết đạp xe và đạp xe, miệng thét lên tiếng rống đau đớn man dại. Để cứu rỗi một linh hồn bất hạnh bị số phận thình lình đánh úp, bạn giúp Vinh tìm ra con đường ngắn nhất để đi từ giao lộ ~1~ tới giao lộ ~N~. Đồng thời, bạn muốn Vinh đi qua các con đường ngắn trước, các con đường dài sau và nghỉ ngơi để lấy sức ở các giao lộ. Cụ thể hơn, gọi độ dài các con đường Vinh đi qua theo thứ tự là ~l_1~, ~l_2, \dots, l_k~; bạn muốn ~l_1 + D \leq l_2~, ~l_2 + D \leq l_3, \dots, l_{k−1} + D \leq l_k~ Hãy giúp Vinh tìm ra con đường ngắn nhất từ giao lộ ~1~ tới giao lộ ~N~ thoả mãn điều kiện trên

Input

• Dòng đầu tiên chứa ba số nguyên ~N~, ~M~, ~D~ ~(1 \leq N~, ~M \leq 2 \times 10^{5}~, − ~10^{9} \leq D \leq 10^{9})~ – số giao lộ, số con đường và hiệu tối thiểu của độ dài con đường liền sau trừ đi độ dài con đường liền trước.
• ~M~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~u~, ~v~, ~c~ ~(1 \leq u~, ~v \leq N~, ~0 \leq c \leq 10^{9})~ miêu tả con đường hai chiều giữa giao lộ ~u~ và giao lộ ~v~ với độ dài ~c~.

Dữ liệu vào đảm bảo mạng lưới giao thông là thông suốt.

Output

Một dòng duy nhất chứa độ dài đường đi ngắn nhất tìm được. In ra "-1" nếu không tồn tại đường đi thoả mãn.

Giới hạn

• Subtask ~1~ ~(20/70~ điểm): ~N~, ~M \leq 1000~
• Subtask ~2~ ~(18/70~ điểm): ~D = 0~
• Subtask ~3~ ~(17/70~ điểm): ~D~ > ~0~
• Subtask ~4~ ~(15/70~ điểm): Không có ràng buộc gì thêm.

Sample Input 1

6 8 -1
1 2 5
1 5 4
5 4 7
2 4 4
2 6 7
4 6 3
2 3 3
3 6 1

Sample Output 1

12

Sample Input 2

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

Sample Output 2

-1

Sample Input 3

4 4 0
1 2 3
2 4 1
1 3 2
3 4 3

Sample Output 3

5

Giải thích

• Trong ví dụ đầu tiên, đường đi tốt nhất là ~1~ ~\rightarrow~ ~2~ ~\rightarrow~ ~4~ ~\rightarrow~ ~6~
• Trong ví dụ thứ hai, có đường đi từ ~1~ tới ~5~ nhưng không có đường đi nào thoả mãn.