Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

GM14P1 - ԳԼԽԱՎՈՐ ՃԱՆԱՊԱՐՀՆԵՐ

Քաղաքը, որտեղ ապրում է Արթուրը, ունի N խաչմերուկ, որոնք միմյանց միացած են ճանապարհներով։ Բոլոր ճանապարհները երկկողմանի են։ Ամեն օր Արթուրը տնից գնում է աշխատանքի և հետո նորից վերադառնում է տուն։ Բայց այդ քաղաքի ճանապարհները այնքան էլ լավը չեն և հաճախ են վերանորոգման ենթարկվում։ Արթուրը նկատեց, որ երբ որոշ ճանապարհներ փակվում են վերանորոգման պատճառով, նա կարողանում է տնից աշխատանքի հասնել ճիշտ նույն ժամանակում, ինչ ժամանակում որ հասնում էր մինչ ճանապարհների փակվելը։ Մյուս կողմից կան նաև այնպիսի ճանապարհներ, որոնց փակման դեպքում տնից աշխատանքի հասնելու ժամանակն աճում է։ Իսկ երբեմն Արթուրն ընդհանրապես չի կարողանում տնից աշխատանքի հասնել։ Այդպիսի ճանապարհներն Արթուրն անվանում է գլխավոր։

Օգնե՛ք Արթուրին գտնել քաղաքի բոլոր գլխավոր ճանապարհները։

Մուտքային տվյալներ

Մուտքի առաջին տողում տրված են N և M բնական թվերը (2 ≤ N ≤ 20 000, 1 ≤ M ≤ 100 000), որոնք իրենցից ներկայացնում են համապատասխանաբար քաղաքի խաչմերուկների և ճանապարհների թիվը:

Հաջորդ M տողերը ինֆորմացիա են պարունակում ճանապարհների մասին։ Յուրաքանչյուր ճանապարհ բնութագրվում է երկու խաչմերուկներով, որոնք այդ ճանապարհը միացնում է և ժամանակով, որն անհրաժեշտ է Արթուրին ճանապարհի մի ծայրից մյուսը հասնելու համար։ Ճանապարհն անցնելու ժամանակը 100000֊ը չգերազանցող բնական թիվ է։ Երկու խաչմերուկներ կարող են միացած լինել մի քանի ճանապարհներով, բայց գոյություն չունի որևէ ճանապարհ, որը խաչմերուկը միացնում է ինքն իրեն։

Եթե բոլոր ճանապարհները հասանելի են, ապա Արթուրը միշտ կարող է տնից հասնել աշխատանքի։

Ելքային տվյալներ

Ելքում պետք է արտածել գլխավոր ճանապարհների K քանակը: 

Օրինակներ՝

N

stdin

stdout

1

2 2
1 2 2
1 2 1

1

2

6 7
1 2 1
2 3 1
2 5 3
1 3 2
3 5 1
2 4 1
5 6 2

2

 


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-10-22
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Գյումրի 2014

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.