Flowery Trails

A national park has $P$ points of interest and $T$ two-way trails that link them. The entrance is point $0$ and the highest peak is point $P-1$.

Visitors walk from the entrance to the highest peak along a shortest path. Different visitors choose different shortest paths, so every shortest path is used by someone. A trail is popular when it lies on at least one shortest path from the entrance to the highest peak.

The park manager plants flowers along both sides of every popular trail, so a popular trail of length $l$ metres needs $2l$ metres of flowers. Compute the total length of flowers needed.

Two points can be linked by more than one trail, and a trail can start and end at the same point. Each trail counts separately, and a popular trail counts once no matter how many shortest paths use it. At least one path from the entrance to the highest peak exists.

The first line has two integers $P$ and $T$.

Each of the next $T$ lines has three integers $p_1$, $p_2$, and $l$, meaning that a two-way trail of length $l$ metres links point $p_1$ and point $p_2$. The two points are not necessarily distinct.

Integers on the same line are separated by a single space.

Print one integer, the total length of flowers in metres.

• $2 \le P \le 10000$, the number of points.
• $1 \le T \le 250000$, the number of trails.
• $1 \le l \le 1000$, the length of a trail.
• $0 \le p_1, p_2 \le P-1$.