Description

There is a postman who needs to deliver items, and the post office is at node $1$. He needs to deliver $n-1$ items, with destinations at nodes $2$ through $n$. Because the city’s traffic is busy, all roads are one-way, with a total of $m$ roads. The postman can carry only one item at a time, and after delivering each item, he must return to the post office. Find the minimum time needed to deliver all $n-1$ items and finally return to the post office.

Input Format

The first line contains two integers, $n$ and $m$, denoting the number of nodes and roads in the city.

From the second line to the $(m+1)$-th line, each line contains three integers $u,v,w$, indicating there is a one-way road from $u$ to $v$ with travel time $w$.

Output Format

Output a single line containing one integer, the minimum required time.

5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2

83

Hint

Constraints:

• For $30\%$ of the testdata, $1 \leq n \leq 200$.
• For $100\%$ of the testdata, $1 \leq n \leq 10^3$, $1 \leq m \leq 10^5$, $1 \leq u,v \leq n$, $1 \leq w \leq 10^4$. The input guarantees that any two nodes can reach each other (the directed graph is strongly connected).

Translated by ChatGPT 5