Invitation Bus Fare Minimization

In this problem, a special bus system is used to distribute invitations. There are \( n \) bus stops and \( m \) one-way bus routes connecting these stops. Each bus route departs from its starting point, reaches its destination, and then returns empty to the starting point.

Every day, all student volunteers start at the headquarters located at bus stop \( 1 \). Each student takes a bus from stop \( 1 \) to a designated bus stop. Every bus stop (from \( 1 \) to \( n \)) is assigned exactly one student. At the end of the day, the buses return to the headquarters empty. Only the passenger-carrying trip costs money. Your task is to compute the minimum total fare needed, i.e. the sum of the minimum costs for a bus to travel from stop \( 1 \) to every stop from \( 1 \) to \( n \>.

You can assume that for every station, there is at least one route from the headquarters (stop \( 1 \)) to that station.

inputFormat

The first line contains two space-separated integers \( n \) and \( m \) \( (1 \leq n \leq 10^5,\ 1 \leq m \leq 10^6) \) representing the number of bus stops and the number of bus routes respectively.

The following \( m \) lines each contain three space-separated integers \( u,\ v,\ w \) \( (1 \leq u,v \leq n,\ 1 \leq w \leq 10^9) \) indicating there is a one-way bus route from stop \( u \) to stop \( v \) with a fare of \( w \).

outputFormat

Output a single integer: the minimum total bus fare required for the students.

sample

3 3
1 2 5
2 3 7
1 3 20

17