Bạn được cho một đồ thị vô hướng, liên thông có trọng số với ~ n ~ đỉnh và ~ m ~ cạnh.

Hãy tìm độ dài đường đi ngắn nhất nhỏ thứ ~ k ~ trong đồ thị đã cho, biết rằng trọng số đường đi là tổng các cạnh đi qua trên đường đi đó. Đường đi từ đỉnh ~ u ~ đến đỉnh ~ v ~ và từ đỉnh ~ v ~ đến đỉnh ~ u ~ được tính là một. Không tính đường đi từ một đỉnh đến chính nó.

Nói cách khác, gọi ~ d ~ là ma trận đường đi ngắn nhất, ~ d_{i,j} ~ ~(1≤i <; j≤n) ~ là độ dài đường đi ngắn nhất từ đỉnh ~ i ~ đến đỉnh ~ j ~. Nhiệm vụ của bạn là tìm giá trị thứ ~ k ~ trong ma trận ~ d ~ sau khi sắp xếp theo thứ tự tăng dần.

Dữ liệu vào

• Dòng đầu tiên gồm 3 số nguyên ~ n,m,k ~ ~(2 ≤ n, m ≤ 10^5, 1 ≤ k ≤ 10^3)~;
• ~ m ~ dòng tiếp theo mỗi dòng chứa 3 số nguyên ~ u,v,c ~ cho biết ~ c ~ ~1 ≤ c ≤ 10^9~(c là trọng số của cạnh ~ (u,v) ~

Kết quả

• Ghi một số nguyên là kết quả của bài toán.

Ràng buộc

• Có 25% test: ~1 ≤ k ≤ 3~;
• Có 25% test: ~n ≤ 10^2~;
• Có 25% test: ~k ≤ 10^2~;
• Có 25% còn lại: Như ràng buộc trong đề bài.

Ví dụ:

Input 1

6 10 5
2 5 1
5 3 9
6 2 2
1 3 1
5 1 8
6 5 10
1 6 5
6 4 6
3 6 2
3 4 5 

Output 1

3 

Input 2

7 15 18
2 6 3
5 7 4
6 5 4
3 6 9
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 2 8
5 3 6
2 5 5
3 7 9
4 1 8
2 1 1 

Output 2

9