require 'pp'
#def pp*args; end

N, M, L = gets.split.map(&:to_i)
E = M.times.map{ # [A, B, C]
	gets.split.map(&:to_i)
}
gets
Q = $<.map{|ln|
	ln.split.map(&:to_i)
}

Town = (1..N).map{|t| {t=>true} }
F = E.sort_by{|a,b,c| c }.inject([]){|acc,(a,b,c)|
	break acc if L < c
	#break acc if Town.size == 1
 	ia, ib = [a,b].map{|_| Town.index{|h| h[_] } }
	#next acc if ia == ib
	Town[[ia,ib].min].update(Town.delete_at([ia,ib].max)) unless ia == ib
	next acc << [a<b ? a:b, a<b ? b:a, c]
}
pp Town
pp F

H = Hash.new{|h,k| h[k]={} }
F.reverse_each{|a,b,c| H[a][b] = c }
g = F.dup
until g.empty?
	g.size.times{
		x, y, z = g.shift
		F.each{|a, b, c|
			next if b != x
			next if L < c+z
			next if H[a][y]
			H[a][y] = c+z
			g << [a, y, c+z]
		}
	}
end
pp H

D = Hash.new{|h,k|
	ds, d, q = [-1]*(N+1), -1, H[k].keys
	ds[k] = 0
	until q.empty?
		d += 1
		q.size.times{
			l = q.shift
			next if ds[l] != -1
			ds[l] = d
			q.concat H[l].keys
		}
	end
	pp [k, ds]
	h[k] = ds
}
p *Q.map{|s,t| s,t = t,s if t<s
	D[s][t]
}
