Farmer John chuẩn bị đi giao bưu kiện cho Farmer Dan. Để giữ hòa bình, ông cho mỗi con bò gặp trên đường một món ngon. Rất tiết kiệm, ông muốn gặp ít bò nhất.

Bản đồ có $N$ chuồng ($1 \le N \le 50,000$), nối bởi $M$ đường hai chiều ($1 \le M \le 50,000$), mỗi đường có $C_{i}$ bò đi dạo ($0 \le C_{i} \le 1,000$). Đường nối hai chuồng khác nhau $A_{i}$ và $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N; A_{i} \ne B_{i}$). Có thể có nhiều đường trực tiếp giữa hai chuồng. FJ ở chuồng 1, Farmer Dan ở chuồng $N$.

Xét bản đồ sau:

           [2]---
          / |    \
         /1 |     \ 6
        /   |      \
     [1]   0|    --[3]
        \   |   /     \2
        4\  |  /4      [6]
          \ | /       /1
           [4]-----[5] 
                3

Đường tốt nhất là 1 → 2 → 4 → 5 → 6, tốn 1 + 0 + 3 + 1 = 5 món.

Cần mang ít nhất bao nhiêu món nếu mỗi con bò khác nhau gặp được nhận đúng một món? Ông không quan tâm độ dài chuyến đi.

Dữ liệu vào

• Dòng 1: hai số nguyên $N$, $M$ cách nhau bởi khoảng trắng.
• Dòng $2..M+1$: ba số nguyên $A_{i}$, $B_{i}$, $C_{i}$ cách nhau bởi khoảng trắng.

Dữ liệu ra

• Dòng 1: số món tối thiểu cần mang.

Ví dụ

Dữ liệu vào 1

6 8
4 5 3
2 4 0
4 1 4
2 1 1
5 6 1
3 6 2
3 2 6
3 4 4

Dữ liệu ra 1

5

Tác giả bài toán: Damon Doucet, 2011