Thành phố Tam Kỳ có \(N\) khu vực tham quan, có \(M\) tuyến đường một chiều giữa các khu vực đó. Tuyến đường thứ \(i\) cho phép đi từ khu vực \(u_i\) đến khu vực \(v_i\), có chi phí di chuyển là \(c_i\). Lưu ý là với mỗi cặp khu vực \(u,\ v\) bất kỳ có thể tồn tại nhiều tuyến đường một chiều từ \(u\) đến \(v\).

Sắp tới là mùa du lịch nên chủ tịch thành phố quyết định tổ chức một cuộc diễu hành thường niên quy mô lớn từ khu vực \(1\) đến khu vực \(N\), rồi sau đó đi ngược lại về khu vực \(1\). Vì chi phí di chuyển cho cả đoàn diễu hành là vô cùng lớn nên ngài chủ tịch muốn cực tiểu nó.

Vì để tối ưu cho việc diễu hành cũng như thuận lợi đi lại cho du khách trong mùa du lịch nên chủ tịch thành phố quyết định cải cách các tuyến đường. Nhưng vì chi phí đang tập trung cho sự kiện diễu hành nên hiện tại chỉ có thể thực hiện 1 cải cách duy nhất: chọn tối đa một con đường rồi đảo chiều của con đường đó. Tức là tuyến đường đi một chiều thứ \(i\) từ \(u_i\) sang \(v_i\) với chi phí \(c_i\) sẽ được chuyển thành đường đi một chiều từ \(v_i\) sang \(u_i\) với cùng mức chi phí \(c_i\). Việc thay đổi này là vĩnh viễn và phải được thực hiện trước cuộc diễu hành. Mỗi con đường có một chi phí riêng để thực hiện việc đổi chiều này, ký hiệu là \(w_i\).

Vì muốn tối ưu chi phí nên ngài chủ tịch quyết định nhờ các bạn ITNBK giúp tính xem phương án tuyến đường đi có tổng chi phí nhỏ nhất từ \(1\) đến \(N\), sau đó về lại \(1\), cộng với chi phí thay đổi một tuyến đường (nếu có) là bao nhiêu. Nếu không có cách nào để di chuyển từ \(1\) đến \(N\) rồi về lại \(1\) (dù đã thay đổi một tuyến đường hay chưa) thì in ra \(-1\).

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(M\) - lần lượt là số khu vực và số tuyến đường giữa các khu vực;
• Tiếp theo là \(M\) dòng, dòng thứ \(i\) trong đó gồm \(4\) số \(u_i,\ v_i,\ c_i,\ w_i\) - trong đó \(c_i\) là chi phí đi từ khu vực \(u_i\) đến khu vực \(v_i\), và \(w_i\) là chi phí để đảo tuyến đường \((u_i,\ v_i)\) thành \((v_i,\ u_i)\).

Output

• In ra một số nguyên duy nhất là tổng chi phí tối thiểu để đi từ \(1\) đến \(N\) sau đó về lại \(1\), cộng với chi phí đảo một tuyến đường (nếu có). Nếu không thể đi thì in \(-1\).

Constraints

• \(2\leq N\leq200,\ 1\leq M\leq50\ 000\);
• \(1\leq u_i,\ v_i\leq N,\ u_i\neq v_i\ (\forall i:\ 1\leq i\leq M)\);
• \(0\leq c_i\leq10^6\ (\forall i:\ 1\leq i\leq M)\);
• \(0\leq w_i\leq10^9\ (\forall i:\ 1\leq i\leq M)\);

Subtasks

• Subtask 1 (20% số điểm): \(M\leq10^3\);
• Subtask 2 (20% số điểm): \(M\) là số chẵn và \(u_{2i-1}=u_{2i},\ v_{2i-1}=v_{2i},\ c_{2i-1}=c_{2i}\ (\forall i:\ 1\leq i\leq\frac{M}{2})\);
• Subtask 3 (20% số điểm): \(c_i=0\ (\forall i:\ 1\leq i\leq M)\);
• Subtask 4 (40% số điểm): Không có ràng buộc gì thêm.

Examples

Sample input 1

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

Sample output 1

10

Note

• Đảo tuyến đường thứ \(2\) (chính là đi từ \(3\) về \(1\) với chi phí là \(1\)), khi đó đường đi có chi phí nhỏ nhất là \(1\rightarrow 2\rightarrow 4\rightarrow 3\rightarrow 1\) với chi phí \(4+2+2+1=9\) thêm phí đảo đường \(1\) là \(10\);

Sample input 2

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

Sample output 2

10

Sample input 3

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

Sample output 3

-1