Tèo đi du lịch từ thành phố \(1\) đến thành phố \(N\) qua một hệ thống giao thông gồm \(N\) thành phố và \(M\) con đường hai chiều kết nối giữa chúng.

Hệ thống giao thông được chia làm hai loại đường:

• Đường cao tốc (ký hiệu loại \(0\)): Không mất phí cầu đường (chi phí bằng \(0\)).
• Đường quốc lộ (ký hiệu loại \(1\)): Có trạm thu phí (chi phí bằng \(1\)).

Hãy giúp Tèo tìm tổng phí cầu đường tối thiểu để đi từ thành phố \(1\) đến thành phố \(N\).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(0 \le M \le 2 \cdot 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, t\) (\(1 \le u, v \le N, t \in \{0, 1\}\)) mô tả một con đường hai chiều nối giữa thành phố \(u\) và \(v\) có loại là \(t\).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng phí cầu đường tối thiểu. Nếu không thể đi tới, in ra \(-1\).

Ràng buộc

Ví dụ

Input:

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

Output:

2