Կտրատիր Գրաֆը

Հեղինեն նվեր է ստացել կշռված գրաֆ՝ կազմված 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 միավոր) Առանց լրացուցիչ սահմանափակումների,

Օրինակ

Մուտք.
3 3
1 2 2
3 2 4
1 3 3

Ելք.
7

Մուտք.
4 5
1 2 -1
2 3 3
3 4 6
4 1 2
1 3 -6

Ելք.
10

Բացատրություն

Առաջին օրինակում K=2 ընտրելու դեպքում գրաֆի բաժանումը կլինի [1,2] և [3], իսկ գումարը կլինի 3+4=7։

Երկրորդ օրինակում K=1 ընտրելու դեպքում գրաֆի բաժանումը կլինի [1,3] և [2,4], իսկ գումարը կլինի -1+3+6+2=10

Աղբյուրը՝ Հանրապետական 2022

Կտրատիր Գրաֆը