Phát biểu bài toán

Cho một đồ thị vô hướng có ~ N ~ đỉnh và ~ M ~ cạnh, mỗi cạnh có độ dài là số nguyên dương. Nhiệm vụ của bạn là:

1. Tính độ dài đường đi ngắn nhất từ đỉnh 1 tới mọi đỉnh trong đồ thị, bao gồm cả đỉnh 1.
2. Tính độ dài đường đi ngắn nhì từ đỉnh 1 tới mọi đỉnh trong đồ thị, bao gồm cả đỉnh 1.

Dữ liệu vào

1. Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ m ~ ~(0 < n, m < 1000)~, lần lượt là số đỉnh và số cạnh của đồ thị.
2. ~ m ~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~ x, y, w ~, biểu diễn cạnh giữa hai đỉnh ~ x ~ và ~ y ~ với trọng số ~ w ~ ~(0 < w < 1000)~.

Dữ liệu ra

• In ra ~ n ~ dòng, mỗi dòng gồm hai số nguyên:
  • Độ dài đường đi ngắn nhất và đường đi ngắn nhì từ đỉnh 1 tới đỉnh ~ i ~.

Ví dụ minh hoạ

Input

3 3
1 2 1
2 3 2
1 3 3

Output

0 2
1 3
3 5

Giải thích

• Từ đỉnh 1:
  • Đường đi ngắn nhất tới đỉnh 1 là ~0~ (đỉnh ban đầu).
  • Đường đi ngắn nhất tới đỉnh 2 là ~1~ (qua cạnh 1-2), đường ngắn nhì là ~3~ (qua cạnh 1-3-2).
  • Đường đi ngắn nhất tới đỉnh 3 là ~3~ (qua cạnh 1-3), đường ngắn nhì là ~5~ (qua cạnh 1-2-3).