Gombóc Artúr sokat jár barátaihoz egy $N$ lakosú városban. Az utcák egyirányúak a városban. Gombóc Artúr nem szeret sokat gyalogolni, így azon töprengett, hogy hány olyan utca van és melyek azok, amiken végigmehet úgy, hogy saját lakásától az egyik barátjához ($N-1$ barátja van, hiszen mindenki a barátja) sétál el az egyik legrövidebb úton. Miután ezen gondolkozott egy keveset, úgy döntött, ideje valami nehezebb munkába fogni, és a következő kérdést tette fel: ,,Hányféleképpen juthatok el a lakásomból az egyes barátaimhoz valamelyik legrövidebb úton?''
A program olvassa be a standard input első sorából $N$-et és $M$-et ($N\mathrm{,}M\le 1000000$): a lakások és az utcák számát, majd a következő $M$ sorból a $k_i$, $v_i$, $s_i$ szóközzel elválasztott egészeket: azaz a $k_i$ lakás kezdőpontú, $v_i$ lakás végpontú, $s_i$ hosszú utcát. Gombóc Artúr lakása az 1. Írjuk a standard output első sorába az $a$ egészet, ahol $a$ db utca a válasz az első kérdésre, majd a következő sorba az $a$ db utcát rendezve (a bemeneti állományban elfoglalt sorszámukkal azonosítva), növekvő sorrendben, szóközzel elválasztva. Az utolsó sorba pedig a második kérdésre válaszként minden barátjára ki kell írni, hogy hányféleképpen lehet oda valamely legrövidebb úton eljutni, illetve ennek a számnak az 1 000 007-es maradékát.