Đường đi ngắn nhất

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một đồ thị vô hướng có trọng số gồm $n$ đỉnh, được đánh số từ $1$ đến $n$.

Mỗi cạnh nối hai đỉnh và có một trọng số nguyên dương biểu thị độ dài của cạnh đó.

Hãy tìm một đường đi có tổng trọng số nhỏ nhất từ đỉnh $1$ đến đỉnh $n$.

Đồ thị có thể chứa khuyên và có thể có nhiều cạnh nối cùng một cặp đỉnh.

Input

Dòng đầu tiên chứa hai số nguyên $n$ và $m$, lần lượt là số đỉnh và số cạnh của đồ thị.

Trong $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $a_i$, $b_i$ và $w_i$, mô tả một cạnh vô hướng nối hai đỉnh $a_i$ và $b_i$ có trọng số $w_i$.

Output

Nếu không tồn tại đường đi từ đỉnh $1$ đến đỉnh $n$, in ra duy nhất số -1.

Ngược lại, in lần lượt các đỉnh của một đường đi ngắn nhất từ đỉnh $1$ đến đỉnh $n$.

Nếu tồn tại nhiều đường đi ngắn nhất, có thể in ra bất kỳ một đường đi nào trong số đó.

Subtask

• Subtask 1 — 15%: $2 \le n \le 4000$; $0 \le m \le 2\cdot10^4$; $1 \le a_i,b_i \le n$; $1 \le w_i \le 10^9$.
• Subtask 2 — 30%: $2 \le n \le 2\cdot10^5$; $0 \le m \le 3\cdot10^5$; $1 \le a_i,b_i \le n$; $1 \le w_i \le 10^9$.
• Subtask 3 — 20%: $2 \le n \le 10^6$; $0 \le m \le 2\cdot10^6$; $1 \le a_i,b_i \le n$; $1 \le w_i \le 20$.
• Subtask 4 — 35%: $2 \le n \le 10^6$; $0 \le m \le 2\cdot10^6$; $1 \le a_i,b_i \le n$; $1 \le w_i \le 10^9$.

Ví dụ

Ví dụ 1

Input

5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1

Output

1 4 3 5

Giải thích

Đường đi được in ra lần lượt đi qua các đỉnh

$1 \rightarrow 4 \rightarrow 3 \rightarrow 5$.

Ba cạnh tương ứng có trọng số lần lượt là $1$, $3$ và $1$, nên tổng độ dài của đường đi bằng

$1+3+1=5$.

Chẳng hạn, đường đi $1\rightarrow2\rightarrow5$ có tổng trọng số $2+5=7$, còn đường đi $1\rightarrow2\rightarrow3\rightarrow5$ có tổng trọng số $2+4+1=7$.

Vì vậy, đường đi được in trong Output có tổng trọng số nhỏ nhất bằng $5$.