Sau những ngày vất vả với các deadline ở trường thì Mạnh đã đăng ký tham gia chương trình mùa hè xanh cùng team. Mọi người sẽ cùng xuất phát tại TPHCM để đến ngọn đồi thiên lý, hoàn thành "hành trình nhật ký yêu thương đời mình". Tuy nhiên, Mạnh "ở vùng quê khu nghèo khó đó có trăm điều khó", vậy nên mọi thứ bạn phải rất tiết kiệm. Mạnh cùng đoàn mở bản đồ ra thì thấy có ~n~ địa điểm và ~m~ chặng đường một chiều nối giữa hai địa điểm nào đó (mỗi chặng đường sẽ có chi phí di chuyển nhất định), trong đó TPHCM có số thứ tự ~1~ còn địa điểm đích đến có số thứ tự ~n~. Cả đoàn được sử dụng thẻ sinh viên đúng một lần để giảm nửa giá vé của một chặng nào đó (từ giá ~a~ xuống còn giá ~[a/2]~). Hãy giúp Mạnh và team tính ra chi phí di chuyển ít nhất để họ sớm đến được ngọn đồi thiên lý nhé.

Input

Dòng đầu tiên có hai số nguyên ~n~ và ~m~, tương ứng là số lượng địa điểm trên bản đồ du lịch và số chặng, trong đó ~2 \leq n \leq 10^5~ và ~1 \leq m \leq 2.10^5~.

Tiếp theo là ~m~ dòng mô tả các chặng đường: mỗi dòng có ba số nguyên ~a,b~ và ~c~ mô tả một chặng bắt đầu tại địa điểm thứ ~a~, kết thúc tại địa điểm thứ ~b~ (với ~a \neq b~) và chi phí là ~c~, trong đó ~1 \leq a,b \leq n~ và ~1 \leq c \leq 10^9~.

Giả sử rằng luôn có thể đi từ TPHCM đến ngọn đồi thiên lý, đồng thời các cặp ~(a,b)~ không nhất thiết phân biệt nhau giữa các dòng.

Output

Một số nguyên là tổng chi phí cần sử dụng của team.

Sample input 1

2 2
1 2 5
1 2 6

Sample output 1

2

Sample Input 2

3 4
1 2 3
2 3 1
1 3 7
2 1 5

Sample Output 2

2

Giới hạn

• Có ~50\%~ số test ứng với ~1 \leq n \leq 20; 1 \leq m \leq 100~.
• Có ~50\%~ số test ứng với ~1 \leq n \leq 10^5; 1 \leq m \leq 2.10^5~.