Oryantiring (hedefler bulunan bir koşu oyunu) oynayan Hızlı Çocuk 1 numaralı hedefte bulunmaktadır, amacı ise N numaralı hedefe ulaşmaktır. Oyun alanında başlangıç ve bitiş hedefleri dahil olmak üzere N farklı hedef vardır. Ayrıca M tane hedef ikilisi arasında doğrudan yol bulunmaktadır. Yollar çift yönlüdür. Her ikili arasında yol bulunmak zorunda değildir, fakat birden fazla yol kullanarak her hedeften diğer tüm hedeflere ulaşılabilir.

Bu M yolun her biri için o yolu alma süresi verilmiştir. Amacımız 1 numaralı düğümden başlayarak N numaralı düğüme en kısa sürede gitmektir.

Bunların dışında Hızlı Çocuk’un sihirli bir iksiri vardır. İksir içindeki suyu bir çeşit güç veren içeceğe dönüştürüyor; eğer Hızlı Çocuk bu iksiri içer ise hızlanıyor.

• Hızlı Çocuk iksiri sadece hedeflerdeyken içebilir, yol ortasında içemez.
• İksir içildiğinde bir sonraki yolu 2 kat hızlı bir şekilde alıyor.
• Eğer iksir dolu ise ağırlık yaptığı için yolları Z süre daha uzun sürede katediyor.
• Yağmur yağdığı için Hızlı Çocuk bir yolu yavaş koşarsa iksirini doldurabiliyor. Eğer bir yolu 2 kat yavaş bir şekilde alırsa iksir doluyor.
• İksirin en fazla bir yolu hızlı almasına yetecek kadar kapasitesi vardır.
• Başlangıçta iksir doludur.

Girdi Biçimi

İlk satırda N, M ve Z değerleri sırasıyla hedef sayısını, yol sayısını ve iksirin yaptığı ağırlığın sebep olduğu yavaşlamayı belirtir.

Sonraki M satırda 3 sayı bulunur: sırasıyla 1. hedef, 2. hedef ve bunların arasında bulunan yolun uzunluğu W_i.

Çıktı Biçimi

Tek bir sayı, cevabın değeri. Sonuç tam sayı çıkmaz ise yukarı yuvarlayınız.

Alt Görevler

• Altgörev 1 (20 puan): 2 <= N <= 10, 1 <= M <= 20, 0 <= Wi, Z <= 100
• Altgörev 2 (17 puan): 2 <= N, M <= 10^5, 0 <= Z <= 10^5, Wi = 2
• Altgörev 3 (17 puan): 2 <= N, M <= 1000, 0 <= Wi <= 100, Z = 10^6
• Altgörev 5 (46 puan): 2 <= N, M <= 10^5, 0 <= Wi, Z <= 10^5

Örnek Girdi 1

5 5 3
3 2 3
1 3 10
1 4 6
2 4 6
2 5 18

Örnek Çıktı 1

20

Örnek 1 Açıklaması

1->3 yolunda iksir kullanarak, 3->2 yolunda iksiri doldurarak, 2->5 yolunda iksiri kullanarak ulaşılır.

Örnek Girdi 2

9 14 4
1 6 29
8 9 16
4 7 9
1 4 8
1 3 9
1 2 10
2 3 20
2 8 19
2 4 29
1 8 40
3 5 16
2 6 24
5 9 15
7 8 2

Örnek Çıktı 2

25