import java.util.Arrays;
import java.util.Scanner;

public class thing {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		int m = in.nextInt();
		int k = in.nextInt();
		int q = in.nextInt();
		
		long[][] mem = new long[k][k];
		long[][] graph = new long[n][n];
		
		for(int i = 0; i < k; i++) {
			Arrays.fill(mem[i], Integer.MAX_VALUE);
		}
		
		for(int i = 0; i < n; i++) {
			Arrays.fill(graph[i], Integer.MAX_VALUE);
			graph[i][i] = 0;
		}
		
		for(int i = 0; i < m; i++) {
			int u = in.nextInt()-1;
			int v = in.nextInt()-1;
			int w = in.nextInt();
			if(u < k && v < k) {
				mem[u][v] = mem[v][u] = w;
			} else {
				graph[u][v] = graph[v][u] = w;
			}
		}
		
		for(int l = 0; l < n; l++) {
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					if(graph[i][l] == Integer.MAX_VALUE || graph[l][j] == Integer.MAX_VALUE) continue;
					graph[i][j] = Math.min(graph[i][j], graph[i][l] + graph[l][j]);
				}
			}
		}
		
		for(int i = 0; i < k; i++) {
			for(int j = 0; j < k; j++) {
				mem[i][j] = Math.min(mem[i][j], graph[i][j]);
			}
		}
		
		for(int l = 0; l < k; l++) {
			for(int i = 0; i < k; i++) {
				for(int j = 0; j < k; j++) {
					mem[i][j] = Math.min(mem[i][j], Math.max(mem[i][l], mem[l][j]));
				}
			}
		}
		
		for(int i = 0; i < q; i++) {
			int a = in.nextInt()-1;
			int b = in.nextInt()-1;
			System.out.println(mem[a][b]);
		}
		
	}

}
