SP26893 PRISTOJBA - Pristojba

In a galaxy far far away there is a new low-cost space carrier starting daily interplanetary flights. In the galaxy there are **N** planets, numbered with integers from 1 to **N**. Cost of a flight between two planets depends only on take-off/landing fees of those planets. For each planet **k** you are given his fee, **p $ _{k} $** , so the cost of a flight between planets **a** and **b** is **p $ _{a} $ + p $ _{b} $** . Space carrier wants to determine the flights it will offer daily so that any planet can be reached from any other planet, directly or indirectly. Because of space reasons it's possible to conduct flights only between certain pairs of planets. Allowed flights are described with **M** permissions of form "**x $ _{k} $ a $ _{k} $ b $ _{k} $** " which means it's possible to conduct a bidirectional flight between planet **x $ _{k} $** and any planet **c**, where **a $ _{k} $** c b $ _{k} $ . Find the minimum total cost of offered flights such that all planets are connected.

N M p $ _{1} $ p $ _{2} $ .. p $ _{N} $ x $ _{1} $ a $ _{1} $ b $ _{1} $ x $ _{2} $ a $ _{2} $ b $ _{2} $ .. x $ _{M} $ a $ _{M} $ b $ _{M} $ 1 For each p $ _{k} $ following holds: 0 For each permission it holds that either x $ _{k} $ < a $ _{k} $ or x $ _{k} $ > b $ _{k} $ . Also, it's possible that some pairs of planets are listed in more than one permission. It will always be possible to choose flights such that all planets are connected.

Minimum daily cost of space carrier transportation system.