{- Author: Robin Nittka -}
{-# OPTIONS_GHC -O2 #-}

module Main
	where

import System.IO
import Data.Graph.Inductive

type Gra = Gr () Int

gras :: [String] -> [Gra]
gras [] = []
gras (line:xs) = mkGraph [(i,()) | i <- [0..m-1]] (map (mkTuple3 . map read . words) a):gras b
	where
		[m,n] = map read $ words line
		(a,b) = splitAt n xs
		mkTuple3 [x,y,z] = (x,y,z)

solve :: Gra -> Int
solve g = (sum $ map third $ labEdges g) - (sum $ map lastEdgeWeight $ msTree $ undir g)
	where
		lastEdgeWeight (LP ((_,w):_)) = w
		third (_,_,x) = x

main :: IO ()
main = do
	file <- openFile "dark.in" ReadMode
	hGetContents file >>= mapM_ (print . solve) . gras . init . lines
