Trung là một thầy thuốc có tiếng bởi tài năng và lòng nhân từ của mình. Sau kì thi VOI vừa rồi, nhiều bạn trẻ cưỡi VOI lần đầu đã tạch ngã rất đau, vì vậy thầy thuốc Trung cần một lượng lớn nguyên liệu để bào chế ra thuốc để chữa cho các bạn.

Vùng Trung ở có ~n~ ngọn núi, được kết nối bởi ~m~ con đường một chiều, trên con đường thứ ~i~ ban đầu có các cây thuốc cho sản lượng ~w_i~. Sau khi hái thuốc ở trên một con đường, các cây thuốc trên con đường này sẽ dần mọc lại nhưng sản lượng sẽ giảm đi một nửa (làm tròn xuống số nguyên gần nhất). Nhà của Trung ở ngọn núi ~1~, tìm lộ trình đi hái được nhiều thuốc nhất (có thể kết thúc ở một ngọn núi bất kì).

Input

• Dòng đầu tiên chứa hai số nguyên ~n, m~ ~(1 \leq n, m \leq 2 \times 10^5)~.

• ~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u, v, w~ ~(1 \leq u, v \leq n; 1 \leq w \leq 10^9)~ mô tả một con đường nối giữa hai ngọn núi.

Output

• In ra số lượng thuốc tối đa Trung có thể thu thập được.

Scoring

Sample Input 1

5 5
1 3 2
3 4 1
4 2 1
2 1 2
3 5 6

Sample Output 1

14

Sample Input 2

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

Sample Output 2

35

Notes

Trong ví dụ, lộ trình Trung có thể đi là ~1 \to 3 \to 4 \to 2 \to 1 \to 3 \to 4 \to 2 \to 1 \to 3 \to 5~ với lượng thuốc thu thập được là ~2 + 1 + 1 + 2 + 1 + 0 + 0 + 1 + 0 + 6 = 14~.