35499번 - 철도계획

국민대학교에는 철도가 없어 많은 학생이 버스를 타고 등하교한다. 학교에서는 학생들의 편의를 위해 새로운 철도망을 구축하기로 했다.

현재 계획된 역 $N$개가 있으며, 철도를 건설할 수 있는 후보 구간 $M$개가 존재한다. 각 철도 구간은 서로 다른 두 역을 양방향으로 연결하며, 이를 건설하여 운행하면 그에 따른 예상 수익을 얻는다.

학교는 $M$개의 후보 구간 중 일부를 선택하여 철도망을 구축하려 한다. 단, 너무 많은 철도를 건설하면 운영상의 문제가 생기므로 다음 규칙들을 반드시 지켜야 한다.

• 노선이란 서로 연결된 철도 구간들의 집합을 의미한다. 두 철도 구간이 하나의 역을 공유한다면 두 구간은 직접 연결되어 있으며, 직접 또는 간접적으로 연결된 모든 철도 구간은 같은 노선에 속한다.
• 여러 개의 독립된 노선이 존재할 수 있으며, 어떠한 노선에도 연결되지 않은 역이 존재할 수 있다.
• 하나의 노선 안에는 순환 경로가 최대 $1$개 존재할 수 있다.
  • 어떤 역에서 출발하여 서로 다른 철도 구간들을 거쳐 출발한 역으로 다시 돌아오는 경로를 순환 경로라고 한다.
  • 두 순환 경로가 다르다는 것은, 경로에 포함된 철도 구간의 집합이 서로 다름을 의미한다.

이 규칙들을 지키면서 철도를 만들 때, 예상 수익의 합의 최댓값을 구해보자.

첫 번째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다.

그다음 줄부터 $M$개 줄에 걸쳐 $u_i, v_i, w_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 철도 구간이 $u_i, v_i$번 역을 양방향으로 연결하며, 이를 건설하여 운행할 경우 예상 수익은 $w_i$임을 의미한다.

첫 번째 줄에 규칙을 지키면서 철도를 만들 때, 예상 수익 합의 최댓값을 출력한다.

• 입력으로 주어지는 모든 수는 정수이다.
• $2 \leq N \leq 100\,000$
• $1 \leq M \leq 200\,000$
• $1 \leq u_i,v_i \leq N$
• $0 \leq w_i \leq 500\,000$
• 두 역 사이에는 최대 하나의 철도 구간만 존재한다.