Rãnh rỗi sinh nông nỗi

View as PDF
Submit solution
Points: 200.00
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
Bob152
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Vào một buổi trưa bình thường như mọi ngày nhưng khác chỗ là trưa nay điện thoại của Bob152 hết pin.Thay vì ngồi khóc và nghĩ về cuộc đời thì nhân ngày 20/10 sắp tới Bob152 muốn làm gì đó để tặng crush của anh ta . Anh ta lấy giấy ra vẽ 1 cái cây gồm ~n~ đỉnh.

Vốn mang tính cách ngáo ngơ nên thay vì vẽ 1 cái cây ~n~ đỉnh ~n-1~ cạnh thì anh ấy vẽ 1 cái cây gồm ~n~ ( ~n \leq 10^5 ~) đỉnh và ~m~ (~ m \leq 10 ^5 ~) cạnh. Bob152 có thể xóa bớt đi ~m - n +1~ cạnh và giữ lại ~n-1~ cạnh tạo thành 1 chiếc cây xinh xắn dễ thương để tặng crush.Nhưng cây bút anh ta đã hết mực nên giờ mà xóa trật 1 cạnh là crush của cậu ấy nay đã xa lại còn xa hơn nữa nên cậu ta rất rén.Biết được sở thích của crush là các số nguyên tố nên Bob152 muốn tạo ra 1 cây có tổng các trọng số của cây tạo ra phải lớn lớn nhất (lớn như tình iu của Bob152 vậy (Trừ test mẫu ra)) và tất cả trọng số của cây đều là số nguyên tố.Trưa nắng gắt Bob152 sợ mình bị hoa mắt xóa nhầm cạnh thì chết dở nên nhờ các bạn lập trình viên tỉnh táo đẹp zai giúp anh ấy làm 1 món quá thật to để tặng crush nhé!

Input:

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

Dòng thứ i của ~m~ dòng tiếp theo chứa 3 số ~u_i , v_i , w_i~ biểu diễn có cạnh 2 chiều nối từ ~u_i~ tới ~v_i~ (~u_i , v_i \leq n~) với trọng số là ~w_i~(~wi \leq 10 ^ 7~).

Output:

1 dòng duy nhất là tổng trọng số của cây thỏa mãn.

Example input: 6 8 1 3 2 3 4 5 1 2 3 4 5 11 3 6 8 6 2 9 6 1 2 6 5 1

Example output: 23

*giải thích: * Cây sau khi bỏ đi m - n +1 cạnh thỏa mãn :

~Subtask ~ ~1~ : ~ n \leq 10.~ (20%)

~Subtask~ ~2 : n \leq 10^3. ~ (20%)

~Subtask~ ~3 :~ Không ràng buộc gì thêm. (60%)

*Lưu ý : * Tất cả các test luôn có nghiệm.

Comments

Please read the guidelines before commenting.


  • -7
    maingocnhat  commented on Oct. 13, 2022, 7:14 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -7
    anhtuan2007  commented on Oct. 12, 2022, 2:42 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -9
    anhtuan2007  commented on Oct. 12, 2022, 11:58 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.