Програмчлалын олимпиадын бодлогын архив

Дарнасус хот нь N хоттой маш том арлын улс юм.  Тэдгээр хотууд нь M ширхэг гүүрээр холбогдсон байдаг. Далайн улс болохоор цунами болон газар хөдлөлт маш их болдог болохоор гүүрнүүд нь маш их гэмтдэг. Саяхан маш хүчтэй газар хөдлөлт болж бүх гүүрнүүд нь нурсан байна.  Тэгээд засгийн газар нь шинэ бодлого хэрэгжүүлэх болсон байна. 

Дахиад газар хөдлөлт болоход хамгийн бага зардлаар засагдах гүүрнүүдийг үлдээгээд бусдыг нь нураахаар шииджээ. Ингэхдээ аль нэг хотоос нь дурын хот хүртэл дор хаяж нэг гүүр байлгахыг хүссэн байна. 1км гүүр засахад  K, харин нураахад P төгрөг зарцуулдаг. Тэгвэл гүүр нураах болон засахад зарцуулах хөрөнгөний абсолют зөрөөг ол. 

K = 1 , P = 1 ээр бодно уу.

Input

Эхний мөрөнд N(0<N<10³*2) болон M(0<M<=( N-1)*N /2) тоо өгөгдөнө.  Дараагийн M мөр тус бүрт A, B,W(0<A<B<=N AND 0<W<10⁵) тоо өгөгдөнө. 

Output

Гүүр нураах болон засахад зарцуулах хөрөнгөний абсолют зөрөө болох нэг эерэг бүхэл тоог хэвлэ.

Example

Input:

8 13

1 2 2
1 3 8
1 4 4
2 3 1
2 5 10
3 5 3
3 6 7
3 4 4
4 7 6
5 6 1
5 8 4
6 7 2
7 8 9

Output:
27