Thuật toán Dijkstra,Bellman–Ford,Floyd Warshall.

Cho đồ thị có hướng có trọng số không âm G= (V, E) được biểu diễn dưới dạng danh sách cạnh trọng số. Hãy viết chương trình tìm đường đi ngắn nhất từ đỉnh s đến tất cả các đỉnh còn lại trên đồ thị. Dữ liệu đảm bảo có đường đi từ đỉnh s tới mọi đỉnh khác trên đồ thị.

Input Format

Dòng đầu tiên là n m và s tương ứng với số lượng đỉnh, cạnh và đỉnh bắt đầu. M dòng tiếp theo là các dòng mô tả cạnh của đồ thị(1<=n<=1000; 1<=m<=n*(n-1)/2; Trọng số các cạnh là số nguyên không âm không vượt quá 100)

Constraints

.

Output Format

In ra đường đi ngắn nhất từ đỉnh u tới mọi đỉnh còn lại.

Ví dụ:

Dữ liệu vào

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

Dữ liệu ra

0 1 3 10 3 6 5