Vé máy bay giảm giá (Flight Discount)

Nguồn: CSES Problem Set

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

Đề bài

Có $n$ thành phố và $m$ chuyến bay một chiều. Chuyến bay từ $a$ đến $b$ có giá $c$.

Bạn cần đi từ thành phố $1$ đến thành phố $n$. Bạn có một phiếu giảm giá và được sử dụng phiếu này cho đúng một chuyến bay trên hành trình. Nếu chuyến bay đó có giá $x$, sau khi dùng phiếu bạn chỉ phải trả

Hãy tìm tổng chi phí nhỏ nhất. Đề bảo đảm luôn tồn tại ít nhất một tuyến từ thành phố $1$ đến thành phố $n$.

Input

Dòng đầu chứa hai số nguyên $n,m$.

Trong $m$ dòng tiếp theo, mỗi dòng chứa $a,b,c$, biểu diễn một chuyến bay một chiều từ $a$ đến $b$ có giá $c$.

Output

In một số nguyên là chi phí nhỏ nhất để đi từ thành phố $1$ đến thành phố $n$ khi sử dụng phiếu giảm giá một lần.

Subtask

Trong tất cả các Subtask: $1\le a,b\le n$; $1\le c\le10^9$; luôn tồn tại đường đi từ $1$ đến $n$.

• Subtask 1 — 20% — 0.30 giây: $2\le n\le100$; $1\le m\le500$.
• Subtask 2 — 30% — 0.60 giây: $2\le n\le5000$; $1\le m\le10^4$.
• Subtask 3 — 50% — 1.00 giây: $2\le n\le10^5$; $1\le m\le2\cdot10^5$.

Ví dụ

Input

3 4
1 2 3
2 3 1
1 3 7
2 1 5

Output

2

Giải thích

Đi $1\to2\to3$. Dùng phiếu cho chuyến $1\to2$ giá $3$, chi phí còn $1$, sau đó trả $1$ cho chuyến $2\to3$. Tổng bằng $2$.