Cho đồ thị vô hướng có ~n~ đỉnh và ~m~ cạnh ~(2 ≤ n ≤ 1000)~. Các đỉnh được đánh số từ 1 đến ~n~. Mỗi cạnh có một trọng số nguyên không âm, có giá trị không vượt quá 1000 và được tô bởi một trong 2 màu đen hoặc đỏ.

Yêu cầu: Tìm đường đi từ đỉnh 1 đến đỉnh ~n~ có tổng trọng số nhỏ nhất và các cạnh đen, đỏ phải lần lượt đan xen nhau trên đường đi, có nghĩa là từ cạnh đen phải đi sang cạnh đỏ và ngược lại.

Dữ liệu vào:

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~m~,
• Mỗi dòng trong ~m~ dòng sau chứa 4 số nguyên ~u,v,k~ và ~c~ xác định có đường nối từ đỉnh ~u~ tới đỉnh ~v~ với trọng số là ~k~ và màu ~c~, trong đó ~c = 0~ là màu đỏ, ~c = 1~ là màu đen,

**Kết quả: **

• Ghi một số nguyên cho biết tổng trọng số nhỏ nhất tìm được hoặc số -1 nếu không tồn tại đường đi.

Ví dụ:

Input:

6 10
1 2 6 1
2 3 2 0
1 3 9 0
1 4 15 1
3 4 2 1
3 5 3 1
3 6 16 1
4 5 5 0
4 6 8 0
5 6 4 1 

Output:

18