Thành phố nơi mà Lợn Trung sống là một thành phố bao gồm n đỉnh và m đường đi 1 chiều giữa các thành phố.  Coi nhà lợn Trung được đánh số 1 và nhà lợn Tuấn được đánh số là n. Lợn Trung muốn xuất phát từ nhà mình và tới nhà lợn Tuấn. Lợn Trung muốn biết trên đường đi này có tất cả bao nhiêu nút mà lợn Trung bắt buộc phải đi qua nếu muốn đến nà Lợn Tuấn trong thời gian ngắn nhất có thể (tính cả nút 1 và nút n). Là một coder tài năng, bạn hãy giúp lợn Trung làm điều này(rất có thể vào tết Trung Thu bạn sẽ nhận được quà từ lợn trung đó).

Dữ liệu vào: Dòng đầu tiên ghi 2 số n,m(n <= 10^5, m <= 10 ^ 6)

m dòng tiếp theo mỗi dòng là bộ 3 số u,v,x chỉ đường đi từ u tới v và mất x giây để đi hết quãng đường trên.

Dữ liệu ra: Số lượng nút cần tìm. Nếu k có đường đi từ 1 tới n thì in ra -1;

Ví dụ : 

INPUT: 2 1

1 2 1

OUTPUT : 2