#1084. PATH - Đường đi ngắn thứ k

Cho một đồ thị vô hướng có trọng số gồm đỉnh và cạnh. Các đỉnh được đánh số từ đến . Bạn hãy tìm đường đi ngắn thứ trong đồ thị này (đường đi từ một đỉnh đến chính nó không được tính, đường đi từ đỉnh đến và từ đến được xem là một). Cụ thể nếu là ma trận đường đi ngắn nhất, ở đó là độ dài đường đi ngắn nhất giữa hai đỉnh và , thì bạn cần đưa ra phần tử thứ của mảng đã được sắp xếp gồm tất cả các .

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên và lần lượt là số đỉnh, số cạnh của đồ thị và giá trị .
• Tiếp theo có dòng, mỗi dòng chứa số nguyên và mô tả một cạnh nối hai đỉnh với trọng số (giữa hai đỉnh bất kỳ có tối đa một cạnh nối chúng).

Dữ liệu ra:

• Một số nguyên là độ dài đường đi ngắn thứ của đồ thị. Dữ liệu vào đảm bảo luôn tồn tại đường đi ngắn thứ .

Ví dụ:

Dữ liệu vào:

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

Dữ liệu ra:

3

Dữ liệu vào:

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

Dữ liệu ra:

9

Giới hạn:

• Có test: ;
• Có test: ;
• Có test: ;
• Có còn lại: Như ràng buộc trong đề bài.