Vương quốc của vua Charles rộng lớn, được chia thành \(n\) khu vực khác nhau, mỗi khu vực được đánh số từ \(1\) đến \(n\). Để di chuyển giữa các khu vực, người dân có thể sử dụng hệ thống đường xá gồm \(m\) con đường. Mỗi con đường nối liền hai khu vực và có một độ dài nhất định.

Nhà vua, vốn sinh sống tại khu vực số \(1\), muốn đến thăm khu chợ lớn ở khu vực số \(n\) để mua sắm và gặp gỡ người dân. Tuy nhiên, nhà vua rất kén chọn đường đi. Ông không thích một số con đường và cũng không muốn phải đi qua những đoạn đường quá dài. Để đáp ứng nguyện vọng của nhà vua, các quan lại trong triều đình đã được giao nhiệm vụ tìm ra một đường đi tối ưu nhất đáp ứng các tiêu chí sau theo thứ tự ưu tiên (tiêu chí đầu tiên được ưu tiên nhất rồi đến tiêu chí thứ hai và cuối cùng là tiêu chí thứ ba):

• Đi qua ít nhất những đoạn đường mà nhà vua không thích.
• Độ dài của đoạn đường dài nhất là nhỏ nhất.
• Tổng độ dài các đoạn đường là nhỏ nhất.

Đầu vào

Dòng đầu tiên chứa hai số nguyên \(n, m\) \((1 \le m \le 2n \le 100000)\).

\(m\) dòng tiếp theo, mỗi dòng chứa \(4\) số nguyên \(u, v, w, p\) \((1 \le u, v \le m, 1 \le w \le 10^9, 0 \le p \le 1)\) với \(w\) là độ dài của đoạn \(uv\) và số nguyên \(p\) mô tả xem nhà vua có không thích đi trên con đường này hay không (bằng \(1\) nếu có và \(0\) trong trường hợp còn lại).

Đầu ra

Một số nguyên duy nhất là tổng độ dài quãng đường từ khu \(1\) tới khu \(n\), nếu không tồn tại đường đi như vậy thì xuất ra số \(-1\).

Subtask

\(50\%\) số test có \(n \le 1000\).

Ví dụ

Đầu vào:

3 3
1 2 4 0
2 3 3 1
3 1 5 1

Đầu ra:

7