O companie feroviară a lansat recent un nou prototip de tren, format dintr-un singur vagon cu N scaune. Scaunele sunt numerotate la 1 la N (numerotarea începe de la partea din față a trenului) și sunt aranjate într-o linie, unul în spatele altuia. Următoarele reguli urmează să fie respectate de fiecare pasager:

1. Pasagerii vor urca în tren doar pe ușa din spate, care este situată după toate scaunele. Odată urcați, pasagerii au dreptul să se deplaseze doar spre partea din față și pot părăsi trenul doar prin ușa din față (care este situată în fața tuturor scaunelor).
2. Fiecare pasager va ocupa locul situat imediat după ultimul scaun ocupat. Dacă trenul este absolut liber, pasagerul va ocupa scaunul din față (marcat ca locul 1).
3. Nici un pasager nu are dreptul să-și părăsească locul până la debarcare.
4. La fiecare stație, pasagerii care au ajuns la destinație părăsesc trenul. Dacă există pasageri pe scaune în fața celui care a ajuns la destinație, ei de asemenea vor părăsi trenul, chiar dacă încă nu au ajuns la destinația lor.
5. Odată ce a ieșit din tren, pasagerul nu mai are dreptul să urce înapoi.

Ruta trenului are M stații, numerotate de la 1 la M. Trenul se oprește în fiecare stație, începând cu stația 1 și terminând cu stația M. La toate cele M stații de tren se află în total N pasageri, numerotați de la 1 la N. Pentru fiecare pasager se cunoaște din timp prețul tichetului, stația de îmbarcare și stația de debarcare.

Compania feroviară dorește să aibă doar clienți fericiți, care ajung la destinația lor. Pentru a avea doar clienți fericiți, compania a permis conductorului să selecteze pasagerii care se pot îmbarca, precum și ordinea în care li se permite îmbarcarea. Astfel, conductorul poate să decidă să nu permită unor pasageri să urce în tren.

Cerința

Determinați profitul maximal care poate fi obținut de companie având doar clienți fericiți, precum și o ordine de îmbarcare validă, care permite obținerea acestui profit.

Date de intrare

Fișierul de intrare train.in conține pe prima linie o pereche de numere N și M. Următoarele N linii descriu datele de călătorie ale fiecărui pasager: câte trei numere întregi x, y și c, unde x reprezintă stația de îmbarcare, y reprezintă stația de destinație și c este costul tichetului.

Date de ieșire

Fișierul de ieșire train.out va avea următorul format:
1. Prima linie va conține un număr P reprezentând profitul maximal pe care îl poate obține compania feroviară;
2. Cea de a doua linie va conține un număr Num reprezentând numărul pasagerilor, care vor putea ajunge la destinația lor în condiția unei soluții optimale, adică a unui profit maximal;
3. Cea de a treia linie va conține indicii pentru fiecare pasager, care ajunge la destinația sa, în ordinea îmbarcării, în soluția optimală determinată. Indicii pasagerilor vor fi separați prin exact un spațiu.

Restricții și precizări

• 1 ≤ N ≤ 100000
• 1 ≤ M ≤ 2 000 000 000
• 1 ≤ x < y ≤ M pentru toți pasagerii
• 1 ≤ c ≤ 10000
• Orice configurație a pasagerilor care produce un profit maximal al companiei este considerată corectă;
• Pentru fiecare test, veți primi 60% punctaj/test pentru scrierea profitului maximal corect P sau 100% punctaj/test pentru scrierea corectă a tuturor valorilor solicitate;
• Pentru 10 puncte, N ≤ 25
• Pentru 30 puncte, 26 ≤ N ≤ 2500
• Pentru 60 puncte, 2501 ≤ N ≤ 100000

Exemplul 1:

train.in

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

train.out

20 
2
1 3

Explicație

Răspunsul corect poate fi obținut astfel:
stația 2: pasagerul 1 urcă în tren
stația 3: pasagerul 3 urcă în tren
stația 6: pasagerul 1 coboară din tren
stația 7: pasagerul 3 coboară din tren

Exemplul 2:

train.in

4 10
1 3 3
1 10 2
2 5 3
1 2 5

train.out

11
3
4 1 3

Explicație

Răspunsul corect poate fi obținut astfel:
stația 1: pasagerul 4 și 1 urcă în tren
stația 2: pasagerul 4 coboară din tren, pasagerul 3 urcă în tren
stația 3: pasagerul 1 coboară din tren
stația 5: pasagerul 3 coboară din tren