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