← Home
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) NextInt() int {
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c >= '0' && c <= '9' {
			break
		}
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		val = val*10 + int(c-'0')
		fs.idx++
	}
	return val
}

type Solver struct {
	k          int
	dsu2       []int
	dsuCC      []int
	dsuCCSize  []int
	par        []int
	parentEdge []int
	lastVisit  []int
	lcaIter    int
	ans        []int64
	pathA      []int
	pathB      []int
}

func NewSolver(n, k int) *Solver {
	s := &Solver{
		k:          k,
		dsu2:       make([]int, n),
		dsuCC:      make([]int, n),
		dsuCCSize:  make([]int, n),
		par:        make([]int, n),
		parentEdge: make([]int, n),
		lastVisit:  make([]int, n),
		ans:        make([]int64, k),
		pathA:      make([]int, 0, 64),
		pathB:      make([]int, 0, 64),
	}
	for i := 0; i < n; i++ {
		s.dsu2[i] = i
		s.dsuCC[i] = i
		s.dsuCCSize[i] = 1
		s.par[i] = -1
		s.parentEdge[i] = -1
	}
	for i := 0; i < k; i++ {
		s.ans[i] = -1
	}
	return s
}

func (s *Solver) find2(v int) int {
	root := v
	for s.dsu2[root] != root {
		root = s.dsu2[root]
	}
	for v != root {
		p := s.dsu2[v]
		s.dsu2[v] = root
		v = p
	}
	return root
}

func (s *Solver) findCC(v int) int {
	v = s.find2(v)
	root := v
	for s.dsuCC[root] != root {
		root = s.dsuCC[root]
	}
	for v != root {
		p := s.dsuCC[v]
		s.dsuCC[v] = root
		v = p
	}
	return root
}

func (s *Solver) makeRoot(v int) {
	v = s.find2(v)
	root := v
	child := -1
	childEdge := -1
	for v != -1 {
		p := -1
		if s.par[v] != -1 {
			p = s.find2(s.par[v])
		}
		pe := s.parentEdge[v]
		s.dsuCC[v] = root
		s.par[v] = child
		s.parentEdge[v] = childEdge
		child = v
		childEdge = pe
		v = p
	}
	s.dsuCCSize[root] = s.dsuCCSize[child]
}

func (s *Solver) mergePath(a, b int, w int64) {
	s.lcaIter++
	pa := s.pathA[:0]
	pb := s.pathB[:0]
	lca := -1
	for lca == -1 {
		if a != -1 {
			a = s.find2(a)
			pa = append(pa, a)
			if s.lastVisit[a] == s.lcaIter {
				lca = a
				break
			}
			s.lastVisit[a] = s.lcaIter
			a = s.par[a]
		}
		if b != -1 {
			b = s.find2(b)
			pb = append(pb, b)
			if s.lastVisit[b] == s.lcaIter {
				lca = b
				break
			}
			s.lastVisit[b] = s.lcaIter
			b = s.par[b]
		}
	}
	for _, v := range pa {
		s.dsu2[v] = lca
		if v == lca {
			break
		}
		eid := s.parentEdge[v]
		if eid >= 0 && eid < s.k && s.ans[eid] == -1 {
			s.ans[eid] = w
		}
	}
	for _, v := range pb {
		s.dsu2[v] = lca
		if v == lca {
			break
		}
		eid := s.parentEdge[v]
		if eid >= 0 && eid < s.k && s.ans[eid] == -1 {
			s.ans[eid] = w
		}
	}
	s.pathA = pa
	s.pathB = pb
}

func (s *Solver) addBridge(a, b, eid int) {
	ca := s.findCC(a)
	cb := s.findCC(b)
	if s.dsuCCSize[ca] > s.dsuCCSize[cb] {
		a, b = b, a
		ca, cb = cb, ca
	}
	s.makeRoot(a)
	s.par[a] = b
	s.parentEdge[a] = eid
	s.dsuCC[a] = b
	s.dsuCCSize[cb] += s.dsuCCSize[a]
}

func (s *Solver) addOurEdge(u, v, eid int) {
	a := s.find2(u)
	b := s.find2(v)
	if a == b {
		return
	}
	s.addBridge(a, b, eid)
}

func (s *Solver) addCompetitorEdge(u, v int, w int64) {
	a := s.find2(u)
	b := s.find2(v)
	if a == b {
		return
	}
	ca := s.findCC(a)
	cb := s.findCC(b)
	if ca != cb {
		if s.dsuCCSize[ca] > s.dsuCCSize[cb] {
			a, b = b, a
		}
		s.makeRoot(a)
		s.par[a] = b
		s.parentEdge[a] = s.k
		s.dsuCC[a] = b
		s.dsuCCSize[s.findCC(b)] += s.dsuCCSize[a]
	} else {
		s.mergePath(a, b, w)
	}
}

func main() {
	in := NewFastScanner()
	n := in.NextInt()
	k := in.NextInt()
	m := in.NextInt()

	s := NewSolver(n, k)

	for i := 0; i < k; i++ {
		u := in.NextInt() - 1
		v := in.NextInt() - 1
		s.addOurEdge(u, v, i)
	}

	for i := 0; i < m; i++ {
		u := in.NextInt() - 1
		v := in.NextInt() - 1
		w := int64(in.NextInt())
		s.addCompetitorEdge(u, v, w)
	}

	var sum int64
	for i := 0; i < k; i++ {
		if s.ans[i] == -1 {
			out := bufio.NewWriterSize(os.Stdout, 1<<20)
			fmt.Fprintln(out, -1)
			out.Flush()
			return
		}
		sum += s.ans[i]
	}

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	fmt.Fprintln(out, sum)
	out.Flush()
}