Royal Questions

중세 왕국에 경제 위기가 휘몰아치고 있다. 우유 방울은 떨어지고, 경제 지표는 나날이 악화되며, 국고의 돈은 사라지고 있다. 상황을 개선하기 위해 King Charles Sunnyface은 자신의 n 아들인 왕자들을 가능한 한 많은 지참금을 가진 신부들과 결혼시키기로 했다.

후보를 찾기 위해 왕은 이웃 왕국들에 문의했고, 얼마 후 m명의 미혼 공주를 데리고 여러 사절단이 도착했다. 손님들을 맞이하던 Karl은 i th 공주의 지참금이 금화 wi개라는 것을 알게 되었다.

이 이야기는 Middle Ages을 배경으로 하지만, 누구도 공주에게 마음에 들지 않는 왕자와 결혼하도록 강요할 수 없다는 진보적인 사상이 사회에 널리 퍼져 있다. 따라서 각 공주는 자신이 아내가 될 의향이 있는 왕자 둘을 선택할 기회가 있다. 왕자들은 운이 좋지 않았으므로 신부를 고르는 문제에서 아버지의 뜻을 따르게 된다.

각 공주의 지참금 액수와 선호를 아는 Charles는 모든 아들의 신부들이 가져오는 지참금의 총합이 가능한 한 커지도록 결혼식을 치르고 싶어 한다. 동시에 모든 왕자나 모든 공주를 결혼시킬 필요는 없다. 각 왕자는 최대 한 명의 공주와 결혼할 수 있으며, 반대로 각 공주도 최대 한 명의 왕자와 결혼할 수 있다.

왕이 국고에 가장 이익이 되는 방식으로 아들들의 혼인을 주선하도록 도와주자.

첫 번째 줄에 두 정수 n, m (2 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000)가 주어진다. 각각 왕자와 공주의 수이다.

이어지는 m개 줄에는 각각 세 정수 ai, bi, wi (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ wi ≤ 10 000)가 주어진다. 이는 i-th 공주가 결혼할 의향이 있는 왕자들의 번호와 그 공주의 지참금 액수이다.

왕이 적절한 결혼식을 치러 얻을 수 있는 금화의 최대 개수를 나타내는 유일한 정수를 출력한다.