Một thành phố có n giao lộ và m đoạn đường nối các giao lộ này, tạo thành hệ thống đường bộ của thành phố. Hai đầu của mỗi đoạn đường luôn nối hai giao lộ khác nhau. Đoạn đường không đi xuyên qua giao lộ nào ở giữa. Vì nhiều lý do, ở giữa một số đoạn đường có đặt thanh chắn giới hạn chiều cao, xe tải không thể đi qua các đoạn đường có thanh chắn.

Thành phố có hai khu chợ quan trọng A và B, lần lượt nằm gần giao lộ 1 và giao lộ n, xe tải cần đi từ A đến B. Hỏi xe tải có thể đến được B không? Nếu có thể, hãy tìm số thanh chắn giới hạn chiều cao ít nhất mà xe phải đi qua?

Dữ liệu vào

Dòng đầu tiên gồm hai số nguyên n, m. Tiếp theo là m dòng, mỗi dòng ba số nguyên u, v, c, biểu thị có một con đường (hai chiều) nối u và v, c=1 nghĩa là đoạn đường đó có thanh chắn giới hạn chiều cao, c=0 nghĩa là không có.

Dữ liệu ra

Nếu không thể đến được, in ra -1; ngược lại in ra số thanh chắn giới hạn chiều cao ít nhất phải đi qua.

Ví dụ

Input

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

Output

1

Ghi chú

Phạm vi dữ liệu

• n, m nằm trong phạm vi hợp lý