Միակ զեղչ
Ալեքսը ապրում է քաղաք
1-ում և ցանկանում է հասնել քաղաք n։ Նա ցանկանում է գտնել այն ավիաչվերթերի հաջորդականությունը, որը կունենա նվազագույն ընդհանուր արժեքը՝ հաշվի առնելով, որ لديه զեղչի կտրոն։ Զեղչի կտրոնը կարելի է օգտագործել միայն մեկ անգամ, որպեսզի որևէ մեկ չվերթի արժեքը կիսով չափ նվազի։ Երբ, օրինակ, նա օգտագործում է այդ կտրոնը այն չվերթի վրա, որի արժեքը x է, ապա վերջնական արժեքը դառնում է ։Մուտք
Մուտքի առաջին տողը պարունակում է երկու ամբողջ թիվ
n և m (), որոնք համապատասխանաբար ցույց են տալիս քաղաքների և չվերթների քանակը։Հաջորդ
m տողերը նկարագրում են չվերթները։ Յուրաքանչյուր տող պարունակում է երեք ամբողջ թվեր a, b և ()՝ նշելով, որ կա երկու ուղղությամբ գործող չվերթ a քաղաքից b քաղաք և обратно, որի արժեքը է։Ելք
Տպեք մեկ ամբողջ թիվ, որը կներկայացնի քաղաք
1-ից քաղաք n հասնելու ամենաէժան երթուղու գինը։Օրինակներ
Մուտք | Ելք |
6 6
1 2 7
2 3 5
3 6 4
1 4 8
4 5 10
5 6 9 | 12 |
Constraints
Time limit: 5.4 seconds
Memory limit: 512 MB
Output limit: 1 MB