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

module Main
	where

import System.IO
import Data.Array
import Data.List
import qualified Data.IntMap as IntMap
import qualified Data.IntSet as IntSet
import qualified Data.Set as Set

type Graph = Array Int [(Int,Int)]
type Distances = Array Int Int

dijkstra :: Graph -> IntMap.IntMap Int -> IntSet.IntSet -> Set.Set (Int,Int) -> IntMap.IntMap Int
dijkstra gr m s pq = case Set.null pq of
		True -> m
		False -> case IntSet.member act s of
			True -> dijkstra gr m s pq'
			False -> dijkstra gr (IntMap.insert act dist m) (IntSet.insert act s) $ foldl followEdge pq' $ gr ! act
	where
		followEdge q (to,w) = Set.insert (dist+w,to) q
		((dist,act), pq') = Set.deleteFindMin pq
	
distances :: Graph -> Int -> Distances
distances gr root = array (bounds gr) $ IntMap.assocs $
		dijkstra gr (IntMap.fromList [ (i,-1) | i <- range $ bounds gr ]) IntSet.empty (Set.singleton (0,root))

solve :: Array Int Int -> Graph -> Int
solve hotels gr = case (distances sgr 1) ! h of
		-1 -> -1
		d -> d-1
	where
		h = snd (bounds hotels) - fst (bounds hotels) + 1
		ds = listArray (1,h) $ map (distances gr) $ elems hotels
		sgr = listArray (1,h) [ [ (j, 1) | j <- [1..h], inRange (0,600) $ ds ! i ! (hotels ! j) ] | i <- [1..h] ]

split :: [String] -> [(Array Int Int, Graph)]
split [] = []
split (n:c:m:x) = (hotels, graph):split b
	where
		(a,b) = splitAt (read m) x
		hotelsList = map head $ group $ sort $ (1:) $ (read n:) $ map read $ tail $ words c
		hotels = listArray (1, length hotelsList) hotelsList
		edges = map (map read . words) a
		graph = array (1,read n) $ map arrange $ groupBy (opFrom (==)) $ sortBy (opFrom compare) $ edges ++ (map flipDir edges) ++ [[i,i,0] | i <- [1..read n]]
		flipDir [x,y,d] = [y,x,d]
		opFrom op (f:_) (f':_) = op f f'
		arrange list@([f,_,_]:_) = (f, [(t,w) | [_,t,w] <- list])

main :: IO ()
main = openFile "hotel.in" ReadMode >>= hGetContents >>= mapM_ (print . uncurry solve) . split . init . lines
