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) \)

Dữ liệu ra

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.

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