Հեղինեն նվեր է ստացել կշռված գրաֆ՝ կազմված N գագաթներից և M կողերից։ Ալեքսն ու Ռոբերտը տեսնելով Հեղինեի նվերը, որոշել են ընտրել որևէ K բնական թիվ և գրաֆը դանակով բաժանել երկու մասի հետևյալ սկզբունքով՝
v համարով գագաթը կլինի առաջին մասում, եթե [(v-1)/K]-ըզույգ է։
v համարով գագաթը կլինի երկրորդ մասում, եթե [(v-1)/K]-ըկենտ է։
([x]-ով նշանակում ենք x-ը չգերազանցող ամենամեծ ամբողջ թիվը) Գրաֆը 2 մասի բաժանելուց հետո Ալեքսն ու Ռոբերտը հաշվելու են այն կողերի կշիռների գումարը, որոնք միացնում են տարբեր մասերի պատկանող գագաթներ։ Նրանք ցանկանում են K թիվը ընտրել այնպես, որ ստացվող գումարը լինի հնարավորինս մեծ։
Պետք է պարզել հնարավոր ամենամեծ գումարը, որ կարող են ստանալ։
Մուտքային տվյալներ
Առաջին տողերում տրված են N և M թվերը (1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000000)Հաջորդ M տողերից յուրաքանչյուրում տրված են լինելու կողը նկարագրող 3 թվեր՝ A[i], B[i], W[i] (1 ≤ A[i], B[i] ≤ N, -109 ≤ W[i] ≤ 109). միացվող գագաթների համարները և կողի կշիռը (A[i] և B[i] թվերը կարող են լինել հավասար, միևնույն A[i], B[i] զույգը կարող է հանդիպել 1-ից ավելի անգամ):
Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ հնարավոր ամենամեծ գումարը։
Ենթախնդիրներ
Ենթախնդիր 0 (0 միավոր) Օրինակները,
Ենթախնդիր 1 (6 միավոր)N ≤ 16
Ենթախնդիր 2 (11 միավոր)N ≤ 100
Ենթախնդիր 3 (24 միավոր)M = N-1, A[i] = i և B[i] = i+1
Ենթախնդիր 4 (59 միավոր) Առանց լրացուցիչ սահմանափակումների,