Sống tại một thành phố lớn có mật độ dân số cao và giao thông phức tạp, ông Bình rất lo về nạn kẹt xe. Để thuận tiện cho việc đi lại, ông Bình đang tìm hiểu các con đường ngắn nhất dẫn từ nhà đến cơ quan. Bạn hãy giúp ông Bình thực hiện công việc khó khăn này.

Bản đồ thành phố gồm có ~N~ nút giao thông và ~M~ con đường hai chiều nối các nút giao thông này. Độ dài của mỗi con đường là một số nguyên dương. Nhà ông Bình ở nút giao thông 1, cơ quan ông Bình ở nút giao thông ~N~.

Yêu cầu: Tìm số lượng đường đi ngắn nhất từ nút 1 đến nút ~N~.

Input

• Dòng thứ nhất ghi hai số nguyên ~N~ và ~M~ (~1 \le N \le 200~, ~1 \le M \le 20000~);
• ~M~ dòng tiếp theo, mỗi dòng ghi 3 số nguyên dương ~U, V, L~ (con đường nối ~U~ đến ~V~ với độ dài ~L~, ~L \le 32000~).

Output

• Gồm một dòng ghi số lượng đường đi ngắn nhất.

Sample Input 1

3 3
1 2 3
1 3 4
2 3 1

Sample Output 1

2