Bờm 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. Bờm 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ử: Bờm đang ở ốc đảo ~1~, về để về đến nhà thì Bờm 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 Bờm đi đoạn đường có độ dài là ~L~, thì Bờm phải mang uống đủ lượng nước là ~L~, bằng không Bờm sẽ chết. Từ đó, người thổ dân đã chỉ cho Bờm cách có thể về nhà: Bờm phải vận chuyển nước từ ốc đảo ~1~ để 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, lại có ~1~ khó khăn khác là: trong bất cứ thời gian nào, Bờm không thể mang lượng nước quá ~C~ (do thể lực có hạn \^_\^).

Yêu cầu: Hãy tìm cách giúp Bờm 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í!!!!)

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~.

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.

Giới hạn

• ~1 \le N~, ~M~, ~C \le 100~
• ~1 \le L \le 30~, ~000~

Sample Input

1
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

Sample Output

65

Note

• Mang ~25~ nước từ ~1~ đến ~2~ sau đó lại quay về ~1~. Do đó, tại ~2~ có ~19~ nước. (Bờm đã 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, Bờm đã mang đến ~2~ thêm ~19~ nước. Sau đó lại từ ~1~, Bờm mang theo ~15~ nước đến ~2~. Vậy khi đến ~2~, Bờm có tại đây ~(19 + 19 + 12 = 50)~ nước.
• Tiếp theo, Bờm 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~, Bờm mang ~25~ nước còn lại đi đến ~3~. Tại ~3~, Bờm có được ~(1 + (25-12) = 14)~ nước.
• Cuối cùng, Bờm mang ~14~ nước đi đến ~5~ rồi đến ~9~. Vậy là Bờm đã thoát khỏi sa mạc.