Mạng dự phòng (Backup Network)

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

Đề bài

Một mạng máy tính gồm $N$ nút và $M$ đường truyền hai chiều.

Đường truyền thứ $i$ nối hai nút $u_i$ và $v_i$, có độ trễ $w_i$.

Cần truyền một gói tin từ nút $1$ đến nút $N$.

Trong toàn bộ hành trình, hệ thống dự phòng được phép kích hoạt nhiều nhất một lần trên đúng một đường truyền mà gói tin đi qua. Khi hệ thống dự phòng được kích hoạt trên đường truyền đó, độ trễ của lần đi qua đường truyền này được tính bằng $0$.

Hãy tìm tổng độ trễ nhỏ nhất có thể để truyền gói tin từ nút $1$ đến nút $N$.

Input

Dòng đầu tiên chứa hai số nguyên dương $N$ và $M$, lần lượt là số nút và số đường truyền.

$M$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $u_i$, $v_i$, $w_i$, mô tả một đường truyền hai chiều nối hai nút $u_i$ và $v_i$ với độ trễ $w_i$.

Có thể tồn tại nhiều đường truyền nối cùng một cặp nút. Không có đường truyền nối một nút với chính nó.

Output

In ra một số nguyên duy nhất $D$:

• nếu tồn tại đường đi từ nút $1$ đến nút $N$, $D$ là tổng độ trễ nhỏ nhất có thể đạt được khi hệ thống dự phòng được sử dụng nhiều nhất một lần;
• nếu không tồn tại đường đi từ nút $1$ đến nút $N$, in ra -1.

Subtask

Trong tất cả các Subtask:

$2\le N\le2\cdot10^5$; $1\le M\le3\cdot10^5$; $1\le u_i,v_i\le N$; $u_i\ne v_i$; $1\le w_i\le10^9$.

• Subtask 1 — 0,8 điểm: $N\le200$; $M\le2000$.
• Subtask 2 — 0,8 điểm: Đồ thị là một cây.
• Subtask 3 — 1,4 điểm: Không có ràng buộc bổ sung.

Ví dụ

Input

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

Output

6

Giải thích

Có thể chọn đường đi:

Độ trễ của ba đường truyền lần lượt là $3$, $3$ và $10$.

Nếu kích hoạt hệ thống dự phòng khi đi qua đường truyền nối $4$ và $5$, độ trễ của đường truyền này được tính bằng $0$.

Tổng độ trễ khi đó là:

Không thể đạt được tổng độ trễ nhỏ hơn, nên đáp án là $6$.