SPOJ in Armenian

Տրված է մայրուղիների ցանց։ Յուրաքանչյուր մայրուղի միացնում է երկու բնակավայր։ Բնակավայրերը համարակալված են 1-ից N թվերով։ Մայրուղիներն իրար հետ հատվում են միայն բնակավայրերում։ Մայրուղիները երկկողմանի են։ Յուրաքանչյուր մայրուղու համապատասխանում է մի ոչ բացասական ամբողջ թիվ, որին անվանենք մայրուղու ծանրաբեռնվածության աստիճան։

Հարկավոր է գտնել 1-ից N-րդ բնակավայր տանող այնպիսի ճանապարհ (մայրուղիներից կազմված շղթա), որում մաքսիմալ ծանրաբեռնվածության աստիճանը լինի որքան հնարավոր է փոքր։

Մուտքը

Մուտքի առաջին տողում տրված են երկու N և M ամբողջ թվեր (1<=N<=1000, 1<=M<=100000)։ Հաջորդ M տողերից յուրաքանչյուրը նակարագրում է մի մայրուղի, առաջին երկու թվերը ցույց են տալիս, թե տվյալ մայրուղին որ բնակավայրերն է իրար միացնում, երրորդ թիվը մայրուղու ծանրաբեռնվածության աստիճանն է, որը 10⁹-ին չգերազանցող ոչ բացասական ամբողջ թիվ է։

Երաշխավորվում է, որ 1-ից N տանող առնվազն մեկ ճանապարհ կա, և, որ ցանկացած երկու բնակավայր միացված են առավելագույնը մեկ մայրուղով։

Ելքը

Ելքում պետք է արտածել մի թիվ՝ 1-ից N տանող ճանապարհի մաքսիմալ ծանրաբեռնվածության մինիմալ հնարավոր արժեքը։

Օրինակ

Մուտքը.
4 5
1 2 5
2 4 4
4 3 9
3 2 2
1 3 3

Ելքը.

4