Description

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.

Input Format

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 Format

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

4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

210 

Hint

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