P1629 Postman Delivers Mail

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**.

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 a single line containing one integer, the minimum required time.

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