競技程式的世界裡有很多城市需要規劃，有的城市要規劃成一些方格，有的城市要是一張正則平面圖，做過無數道城市規劃題目的你，覺得競程選手根本是城市規劃師。

正如題目名稱所說，你又要規劃一個城市了！王董最近買了一片新的土地，要在上面建造一個城市，幸運的是，他早就把城市設計好了：這座城市有 $N$ 個區域和 $M$ 條道路，每條道路都雙向連接兩座城市，王董需要做的就只是先請道路建設公司來把道路都蓋好，之後人們就會自己搬入各個區域。

道路建設公司提供限時優惠方案，如果請他們在第 $s_i$ 天到第 $t_i$ 天之間（包含 $s_i,t_i$）建造第 $i$ 條道路，那麼費用全免，否則建造一條道路要花 1 塊錢。一條道路需要花費一整天的時間建造，且同一天只能建造一條道路。

雖然王董其實有錢在沒有優惠的情況下請道路建設公司建造所有道路，但錢畢竟還是能省則省，才能做更多好玩的事情，因此，他想知道至少要花多少錢建造道路，才能使得整座城市的 $N$ 個區域連通，也就是從任一個區域都能直接或間接地透過有建造的道路，到達其他任何一個城市。與此同時，他還想知道在最小化花費的錢的情況下，要使用優惠方案建造的道路有哪些。