傳智專修學(xué)院里有 n 棟教學(xué)樓，有 m 條雙向通行道路連接這些教學(xué)樓，不存在重邊和自環(huán)。每條道路都有一定的長度，而且所有教學(xué)樓之間都可以直接或者間接的通過道路到達(dá)。我們可以很容易的求出這些教學(xué)樓之間的最短路。

為了使交通更為順暢，校方?jīng)Q定在兩個教學(xué)樓里增設(shè)一對傳送門。傳送門可以將這對教學(xué)樓的距離直接縮短為 0。利用傳送門，某些教學(xué)樓之間的最短路的距離就變短了。

由于預(yù)算有限，學(xué)校里只能安裝一對傳送門。但是校長希望盡可能方便學(xué)生，使任意兩點之間的最短路長度的總和最小。當(dāng)然啦，從 x 教學(xué)樓到 y 教學(xué)樓的長度和從 y 教學(xué)樓到 x 教學(xué)樓的長度只需要統(tǒng)計一次就可以了。

輸入第 1 行兩個正整數(shù) n,m(n<=100,m<=1/2*n*(n-1)，代表教學(xué)樓和道路數(shù)量。

接下來 m 行，每行三個正整數(shù) Xi,Yi,Wi，表示在教學(xué)樓Xi 和 Yi 之間，有一條長度為 Wi 的道路。

4 5
1 2 3
1 3 6
2 3 4
2 4 7
3 4 2

14