P1342 [CERC1998] Invitation Cards

In the television era, few people watch stage plays. The antique comedians of Malidinesia noticed this and want to promote the theater, especially the quaint comedies.

They have printed invitation cards and all the necessary information and plans. Many students are hired to distribute these invitations. Each student volunteer is assigned exactly one bus stop where he or she will stay for the whole day, inviting people to participate. The bus system here is very special: there are $n$ stops and $m$ routes; all routes are one-way, connecting two stops. A bus departs from its origin and, after reaching its destination, returns empty to its origin. Each morning, the students depart from the headquarters at stop $1$, take buses to their assigned stop, and invite passengers there. Exactly one student is scheduled at each stop. At the end of the day, all students return to the headquarters. Now you need to find the minimal possible sum of bus fares required for the students.

The first line contains two integers $n$ and $m$. Lines $2$ through $m + 1$ each contain three integers $u, v, w$, indicating that there is a one-way route from $u$ to $v$ with fare $w$.

Output a single line with one integer, the minimal total fare.

Constraints For $100\%$ of the testdata, it is guaranteed that: - $1 \leq n, m \leq 10^6$. - $1 \leq u, v \leq n$, $1 \leq w \leq 10^9$. - Every stop is reachable from $1$. Translated by ChatGPT 5