Անկարգություններ և ուղիներ

Ենթադրենք կա մի երկիր, ուր կա n քաղաք և m ճանապարհ, որոնք կապում են այդ քաղաքները: Յուրաքանչյուր ճանապարհի առնչությամբ տրված է հավանականությունը (0 ≤ ≤ 1), թե այն բաց կլինի ընթացող անկարգությունների պատճառով: Քաղաքները միշտ բաց են: Ձեր խնդիրն է պարզել, թե քաղաք 1-ից դեպի քաղաք n տանող որ ուղին ունի բաց լինելու ամենաբարձր հավանականությունը, հաշվի առնելով ճանապարհների հավանականությունները: Եթե քաղաք 1-ից դեպի քաղաք n ուղի չի գտնվում, ապա հավանականությունը համարում ենք 0:

Գրեք ծրագիր, որը կհաշվարկի, թե որ ուղին է տալիս քաղաք 1-ից քաղաք n հասնելու առավելագույն հավանականությունը:

Մուտք

Առաջին տողում տրված են երկու ամբողջ թիվ n և m (1 ≤ n ≤ 10 000, 1 ≤ m ≤ 20 000), որոնք ցույց են տալիս քաղաքների քանակը և ճանապարհների քանակը, համապատասխանաբար:

Հաջորդ m տողերից յուրաքանչյուրում հասանելի են երեք ամբողջ թվեր , և (, )։ Այդ թվերը ցույց են տալիս, որ կա ճանապարհ քաղաքից դեպի քաղաք, իսկ -ը տվյալ ճանապարհի բաց լինելու հավանականությունն է:

Ելք

Արդյունքում պետք է տպել մեկ πραγμα թիվ, որը ցույց է տալիս ճանապարհի բաց լինելու առավելագույն հավանականությունը՝ քաղաք 1-ից քաղաք n շարժվելու համար: Պատասխանը ճիշտ կհանդเสีย, եթե այն շեղվում է իրական արժեքից առավելագույնը 1e-5-ով:

Օրինակներ