An đang thám hiểm một hệ thống hầm ngầm gồm có \(N\) căn phòng (được đánh số từ \(1\) đến \(N\)) và \(M\) cửa một chiều kết nối giữa chúng. Một số cửa đang ở trạng thái mở sẵn, An có thể đi qua mà không tốn công sức (chi phí bằng \(0\)). Một số cửa khác đang bị khóa, An cần phải gạt công tắc kích hoạt cơ cấu mở cửa để đi qua (chi phí bằng \(1\)).

Hãy tìm số lần gạt công tắc tối thiểu để An có thể di chuyển từ phòng \(1\) đến phòng \(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, w\) (\(1 \le u, v \le N, w \in \{0, 1\}\)) mô tả một cửa một chiều từ phòng \(u\) sang phòng \(v\). Nếu \(w = 0\), cửa mở sẵn. Nếu \(w = 1\), cửa đang bị khóa.

Định dạng đầu ra

• Một số nguyên duy nhất là số lần gạt công tắc tối thiểu. Nếu không thể đi từ phòng \(1\) đến phòng \(N\), 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