Siro vô tình bị lạc vào trong ~1~ ốc đảo có ~1~ bộ tộc thổ dân sinh sống trong ~1~ lần đi qua sa mạc. Siro muốn thoát khỏi sa mạc để về nhà. Người thổ dân đã cho anh một bản đồ vùng sa mạc này.

Sa mạc gồm ~N~ ốc đảo, ~M~ đường đi an toàn nối với nhau và tại mỗi ốc đảo lại có ~1~ hồ chứa nước rất lớn và nước chứa trong các hồ này không bao giờ cạn. Tuy nhiên hiện tại, không có nước trong các hồ.

Giả sử:

• Siro đang ở ốc đảo ~1~, về để về đến nhà thì Siro phải đi đến ốc đảo ~N~. Người thổ dân cho biết rằng tại vùng sa mạc này, nếu Siro đi đoạn đường có độ dài là ~L~, thì Siro phải mang uống đủ lượng nước là ~L~, bằng không Siro sẽ chết.
• Từ đó, người thổ dân đã chỉ cho Siro cách có thể về nhà: Siro phải vận chuyển nước từ ốc đảo ~1~ đển tích trữ trong các hồ tại những ốc đảo khác bằng các con đường an toàn đã có, từ đó anh có thể về nhà.
• Tuy nhiên, vì thể lực có hạn nên trong bất cứ thời gian nào, Siro không thể mang lượng nước quá ~C~.

Yêu cầu: Hãy tìm cách giúp Siro về nhà nhưng đồng thời sử dụng ít nước nhất (do trong sa mạc, nước rất quý giá!)

Input

Dòng đầu tiên gồm một số nguyên ~T~ cho biết số lượng test, mỗi test có dạng như sau:

• Dòng đầu tiên là 3 số nguyên ~N, M, C~ ngăn cách nhau bởi khoảng trắng;
• ~M~ dòng tiếp theo mỗi dòng gồm 3 số nguyên ~i, j, L~ với ý nghĩa có đường đi từ ốc đảo ~i~ đến ốc đảo ~j~ và ngược lại là an toàn và có độ dài ~L~.

Giới hạn:

• ~(1 \le T \le 10)~
• ~(1 \le N, M, C \le 100)~
• ~(1 \le L \le 30,000)~

Output

Với mỗi bộ test xuất ra đúng ~1~ số nguyên chỉ lượng nước ít nhất cần dùng, nếu không có đường về nhà thì in ra ~-1~.

Sample

Input #1

2
9 10 25 
1 2 3 
2 3 12 
3 4 4 
3 5 9 
4 9 13 
5 9 5 
2 6 10 
6 7 10 
7 8 10 
8 9 10
4 3 100
1 2 49
2 3 49
3 4 49

Output #1

65
2499

Hint

Giải thích test1 của #1:

• Mang ~25~ nước từ ~1~ đến ~2~ sau đó lại quay về ~1~. Do đó, tại ~2~ có ~19~ nước. (Siro đã uống hết ~(3 + 3)~ nước trong lần đi và về, ~(19 = 25–3–3)~).
• Lặp lại như thế ~1~ lần nữa, Siro đã mang đến ~2~ thêm ~19~ nước. Sau đó lại từ ~1~, Siro mang theo ~15~ nước đến ~2~. Vậy khi đến ~2~, Siro có tại đây ~(19 + 19 + 12 = 50)~ nước.
• Tiếp theo, Siro lại mang ~25~ nước đi từ ~2~ đến ~3~, rồi quay về ~2~, như vậy, tại ~3~ có ~(25 – 12 – 12 = 1)~ nước. Từ ~2~, Siro mang ~25~ nước còn lại đi đến ~3~. Tại ~3~, Siro có được ~(1 + (25 - 12) = 14)~ nước.
• Cuối cùng, Siro mang ~14~ nước đi đến ~5~ rồi đến ~9~.

Vậy là Siro đã thoát khỏi sa mạc.