Տրանսպորտային ծանրաբեռնվածությունը
Տրված են
n քաղաքներ, որոնք միմյանց միացված են m ճանապարհներով։ Յուրաքանչյուր ճանապարհ հանդիսանում է տրանսպորտային երթուղի և ունի ծանրաբեռնվածության արժեք, որն արտահայտում է տվյալ ճանապարհի խտությունը։Ձեր խնդիրն է յուրաքանչյուր քաղաք
i-ի համար որոշել, թե ինչի՞ն է հավասար քաղաք 1-ից քաղաք i տանող երթևեկության նվազագույն հնարավոր ծանրաբեռնվածությունը։ Ճանապարհի ընդհանուր ծանրաբեռնվածությունը սահմանվում է որպես տվյալ ուղու վրա հանդիպող ծանրաբեռնվածության առավելագույն արժեքը։Մուտք
Մուտքի առաջին տողում տրվում են երկու ամբողջ թիվ,
n և m (), որոնք ցույց են տալիս քաղաքների քանակը և ճանապարհների քանակը, համապատասխանաբար:Հաջորդ
m տողերից յուրաքանչյուրում տրված են երեք ամբողջ թիվ և (), որոնք նկարագրում են մի ճանապարհ՝ կապող քաղաք a_i-ը և քաղաք b_i-ը ծանրաբեռնվածությունը w_i արժեքով։Ելք
Ելքում պետք է տպել մեկ տող, որը պարունակում է
n-1 ամբողջ թիվ (բացատներով բաժանված), որտեղ i-րդ թիվը ցույց է տալիս քաղաք 1-ից մինչև քաղաք i+1 տանող երթևեկության նվազագույն հնարավոր ծանրաբեռնվածությունը։Օրինակներ
Մուտք | Ելք |
5 5
1 2 5
1 3 2
4 5 10
4 3 6
1 5 9 | 5 2 6 9 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB