Hành tinh Marvelous Land gồm n thành phố, được kết nối với nhau bởi m tuyến đường hai chiều. Giữa hai thành phố chỉ có tối đa một tuyến đường nối chúng và không có tuyến đường nào nối một thành phố tới chính nó. Các thành phố được đánh số từ 1 tới ~n~. Trong đó có 2 thành phố là trung tâm kinh tế quan trọng là thành phố 1 và thành phố ~n~. Tuyến đường thứ ~i~ cho phép đi lại giữa hai thành phố ~u_i~ và ~v_i~ với ~t_i~ đơn vị thời gian. Một ngày nọ, người dân Marvelous Land khảo sát các con đường và nhận thấy rằng cần nâng cấp mạng lưới đường hiện có, hoặc xây thêm một số tuyến đường hai chiều. Điều cần quan tâm nhất là tổng thời gian ngắn nhất để đi lại giữa 2 thành phố trung tâm kinh tế. Trước khi quyết định nâng cấp mạng lưới đường đi, cần xác định các tuyến đường trọng yếu là những tuyến đường mà không thể không đi qua khi muốn đi từ thành phố 1 tới thành phố ~n~ với tổng thời gian ngắn nhất.

Yêu cầu: Đếm số lượng tuyến đường trọng yếu.

Dữ liệu vào:

• Dòng đầu ghi hai số nguyên ~n~ và ~m~ ~(1≤n≤10^5;1≤m≤2×10^5)~, số thành phố và số tuyến đường.
• ~m~ dòng tiếp theo, mỗi dòng ghi ba số nguyên, dòng thứ ~i+1~ ghi số ~u_i,v_i,t_i~ ~(1≤u_i,v_i≤ n,1≤t_i≤10^6)~ là các thông tin của tuyến đường thứ ~i~.

Output: ghi duy nhất một số nguyên là số tuyến đường trọng yếu.

Ràng buộc: 50% số điểm của bài tương ứng với các test có ~n≤1000~ và ~m≤1000~.

Ví dụ:

Input

8 9
1 2 3
1 3 1
2 4 4
3 4 7
5 4 9
8 6 5
8 7 4
6 5 2
7 5 3 

Output

3