Tách Mạng Thành Hai Vùng

Có $n$ điểm dân cư và $m$ tuyến đường hai chiều. Tuyến đường nối $u$ với $v$ có chi phí duy trì $w$. Mạng ban đầu liên thông.

Bạn cần giữ lại một số tuyến đường sao cho:

• toàn bộ điểm dân cư được chia thành đúng hai nhóm không rỗng;
• trong mỗi nhóm, mọi cặp điểm đều đi được tới nhau chỉ bằng các đường được giữ;
• không cần giữ đường nối giữa hai nhóm.

Hãy tìm tổng chi phí duy trì nhỏ nhất của các đường còn lại.

Input

• Dòng đầu chứa hai số nguyên $n,m$.
• Mỗi dòng trong $m$ dòng tiếp theo chứa ba số nguyên $u,v,w$, mô tả một tuyến đường vô hướng.

Output

• In một số nguyên - tổng chi phí nhỏ nhất sau khi tách mạng thành đúng hai nhóm.

Constraints

• $2\le n\le 10^5$.
• $1\le m\le 10^6$.
• $1\le u,v\le n,u\ne v$.
• $1\le w\le 1000$.
• Mạng ban đầu liên thông; có thể có nhiều tuyến đường giữa cùng một cặp điểm.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 8,m\le 14$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

10