Một thành phố có $n$ giao lộ và $m$ đoạn đường hai chiều nối các giao lộ. Mỗi đoạn đường có một độ dài; ở giữa một số đoạn đường có đặt thanh chắn giới hạn chiều cao, xe tải không thể đi qua các đoạn đường có thanh chắn.

Thành phố có hai khu chợ quan trọng A và B, lần lượt nằm ở giao lộ $1$ và giao lộ $n$. Hiện tại xe tải luôn có thể đi từ A đến B mà không phải qua thanh chắn nào.

Để rút ngắn quãng đường vận chuyển, thành phố quyết định dỡ bỏ tối đa $2$ thanh chắn. Hỏi sau khi dỡ bỏ, quãng đường ngắn nhất để xe tải đi từ A đến B giảm được nhiều nhất bao nhiêu?

Dữ liệu vào

Dòng đầu tiên gồm hai số nguyên $n, m$.

Tiếp theo là $m$ dòng, mỗi dòng gồm bốn số nguyên $a, b, c, d$: có một đoạn đường hai chiều nối giao lộ $a$ và giao lộ $b$, độ dài $c$. Nếu $d = 1$ thì đoạn đường có thanh chắn, nếu $d = 0$ thì không có.

Dữ liệu ra

In ra một số nguyên là độ dài quãng đường ngắn nhất giảm được nhiều nhất.

Ví dụ

Input

5 7
1 2 3 0
2 5 6 0
1 3 1 1
3 5 1 1
1 4 4 0
4 5 4 0
2 4 2 1

Output

6

Ghi chú

Giải thích ví dụ

Khi chưa dỡ thanh chắn, đường ngắn nhất là $1 \to 4 \to 5$ dài $8$. Dỡ bỏ thanh chắn trên hai đoạn $1 - 3$ và $3 - 5$ thì có đường $1 \to 3 \to 5$ dài $2$, giảm được $8 - 2 = 6$.

Phạm vi dữ liệu

• $2 \le n \le 10^4$, $1 \le m \le 10^4$
• $1 \le a, b \le n$, $1 \le c \le 1000$, $d \in {0, 1}$
• Dữ liệu bảo đảm khi không đi qua thanh chắn nào vẫn có đường từ giao lộ $1$ đến giao lộ $n$.