Volgende halte

Volgende halte: Centraal Station, a.k.a The Goat.

Aceasta este vocea monotonă, dar reconfortantă, pe care Algorel o aude în fiecare dimineață. Deși și-a îndeplinit visul de a studia în străinătate, realitatea l-a lovit rapid: în „Țara Bicicletelor”, iarna nu e ca acasă, iar vântul tăios de la Marea Nordului l-a convins că mersul pe bicicletă este un sport extrem pentru care nu e încă pregătit. Din această cauză, Algorel va trebui să ia autobuzul până la universitate.

Cerință

Ruta sa are $N$ stații. El pleacă din stația $1$ și trebuie să ajungă în stația $N$. Există $M$ autobuze disponibile. Fiecare autobuz $i$ este caracterizat de:

• $s_i$ – stația fixă de unde poate urca în acest autobuz;
• $d_i$ – distanța maximă (în număr de stații); autobuzul poate opri în orice stație $j$, astfel încât $s_i < j \leq s_i + d_i$;
• $c_i$ – costul biletului pentru o călătorie (indiferent de stația la care coboară).

Ajutați-l pe Algorel să găsească o combinație de autobuze care să îl ducă la universitate și să aibă costul total minim. Dacă există mai multe variante de cost minim, se va alege oricare soluție ce folosește un număr minim de autobuze (schimburi minime).

Nu uitați! Este o cauză nobilă: dacă îl ajutați să economisească bani, va avea cu ce să își plătească căldura în casă.

Date de intrare

Fișierul de intrare volgende.in are următoarea structură:

• Pe prima linie se află două numere naturale, $N$ și $M$, reprezentând numărul de stații, respectiv numărul de autobuze.
• Pe următoarele $M$ linii se află câte 3 numere naturale $s_i, d_i, c_i$, reprezentând caracteristicile fiecărui autobuz.

Date de ieșire

Fișierul de ieșire volgende.out va avea următoarea structură:

• Pe prima linie se vor afla două numere naturale, $C$ și $K$, unde $C$ este costul minim total, iar $K$ este numărul de autobuze folosite.
• Pe a doua linie se vor afla $K$ numere naturale, separate printr-un spațiu, reprezentând indicii autobuzelor folosite (în ordinea utilizării lor, numerotate de la $1$ la $M$ conform fișierului de intrare).

Restricții și precizări

• $1 \leq N, M \leq 100 \ 000$;
• $1 \leq s_i < N$;
• $1 \leq d_i \leq N - s_i$;
• $0 \leq c_i \leq 10^{9}$;
• Fiecare drum trebuie să înceapă cu un autobuz ce pornește din stația $1$ și să se încheie cu unul care se poate opri în stația $N$;
• Se garantează că există întotdeauna drum de la stația $1$ la stația $N$;
• În cazul în care numai costul este corect, se va acorda 40% din punctaj;
• În cazul în care costul și numărul de autobuze sunt corecte, dar drumul este greșit/lipsește, se va acorda 60% din punctaj;
• În cazul în care costul, numărul de autobuze și drumul sunt corecte, se va acorda 100% din punctaj;

Exemplu

volgende.in

10 8
6 4 4
4 4 4
6 4 10
5 2 1
1 5 3
7 3 3
6 1 6
1 9 15

volgende.out

7 2
5 1

Explicație

Drumul optim este format din autobuzele $(5,1)$, având costul $3+4=7$ și $2$ autobuze. Alte două drumuri interesante sunt:

• Varianta $(5,4,6)$, care are tot costul $7 = (3+1+3)$, dar folosește $3$ autobuze.
• Varianta $(8)$, care are costul $15$ și folosește un singur autobuz.