傳智專修學(xué)院里有 n 棟教學(xué)樓，有 m 條雙向通行道路連接這些教學(xué)樓，不存在重邊和自環(huán)。每條道路都有一定的長度，而且所有教學(xué)樓之間都可以直接或者間接的通過道路到達(dá)。我們可以很容易的求出這些教學(xué)樓之間的最短路。
為了使交通更為順暢，校方?jīng)Q定在兩個(gè)教學(xué)樓里增設(shè)一對(duì)傳送門。傳送門可以將這對(duì)教學(xué)樓的距離直接縮短為 0。利用傳送門，某些教學(xué)樓之間的最短路的距離就變短了。
由于預(yù)算有限，學(xué)校里只能安裝一對(duì)傳送門。但是校長希望盡可能方便學(xué)生，使任意兩點(diǎn)之間的最短路長度的總和最小。當(dāng)然啦，從 x 教學(xué)樓到 y 教學(xué)樓的長度和從 y 教學(xué)樓到 x 教學(xué)樓的長度只需要統(tǒng)計(jì)一次就可以了。
輸入第 1 行兩個(gè)正整數(shù) n,m(n<=100,m<=1/2*n*(n-1)，代表教學(xué)樓和道路數(shù)量。
接下來 m 行，每行三個(gè)正整數(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