class No {
	No next ;
	Caverna posicao ;
	No (Caverna posicao) {
		this.posicao = posicao ;
	}

}
class Caverna {
	int distancia = Integer.MAX_VALUE ;
	Lista2 dist = new Lista2 () ;
	int numero ;
	int pontosPerdidos = 0;
	int pontosVida ;

	Lista adj = new Lista () ;
	boolean marcado = false ;
}
class Lista {
	No inicio ;
	No fim;

	public void inserir (No no) {
		if (inicio == null) {
			inicio = no ;
			fim = inicio ;
		}
		else {
			fim.next = no ;
			fim = fim.next ;
		}
	}
}
class No2 {
	int dist ;
	No2 next ;
	public No2(int dist) {
		this.dist = dist ;
	}


}
class Lista2 {
	No2 inicio ;
	No2 fim ;
	public void inserir (int no) {
		if (inicio == null) {
			inicio = new No2(no) ;
			fim = inicio;
		}
		else {
			fim.next = new No2(no) ;
			fim = fim.next ;
		}
	}
}
class Grafo {
	Caverna inicio ;
	int fim ;
}


public class L3QD {
	Arquivo arq = new Arquivo("L3QD.in","L3QD.out");
	int numeroElementos = 0 ;
	Caverna[] heap ;
	int contador = 1 ;
	StringBuffer buffer ;
	String nl;
	boolean [] calculado ;
	public L3QD () {
		while (!arq.isEndOfFile()) {
			buffer = new StringBuffer();
			buffer.append("Caso #");
			buffer.append(contador);
			nl = System.getProperty("line.separator");
			buffer.append(nl);
			numeroElementos = 0;
			int n = arq.readInt () ;
			int m = arq.readInt();
			int l = arq.readInt();
			int t = arq.readInt();
			Caverna[] cavernas = new Caverna[n];


			for (int i = 0 ; i < m ; i++) {
				int ini = arq.readInt();
				if (cavernas[ini] == null) {
					cavernas[ini] = new Caverna();
					cavernas[ini].numero = ini ;
				}
				int sai = arq.readInt();
				if (cavernas[sai] == null) {
					cavernas[sai] = new Caverna ();
					cavernas[sai].numero = sai ;
				}
				cavernas[ini].adj.inserir(new No(cavernas[sai]));
				cavernas[sai].adj.inserir(new No(cavernas[ini]));
				int y = arq.readInt();
				cavernas[ini].dist.inserir(y);
				cavernas[sai].dist.inserir(y);
			}
			for (int i = 0; i < t; i++) {
				int cav = arq.readInt();
				int p = arq.readInt();
				cavernas[cav].pontosPerdidos += p ;
			}
			heap = new Caverna[n];
			cavernas[0].distancia = 0 ;
			inserir(heap,cavernas[0]);
			cavernas[0].pontosVida = l - cavernas[0].pontosVida ;
			algoritmo(cavernas);
			for (int i = 0; i < n; i++) {
				if (cavernas[i].pontosVida <= 0 || cavernas[i].distancia == Integer.MAX_VALUE ) {
					buffer.append("Morte certa");
					buffer.append(nl);
				}
				else {
					buffer.append(cavernas[i].distancia);
					buffer.append(" ");
					buffer.append(cavernas[i].pontosVida);
					buffer.append(nl);
				}
			}
			arq.print(buffer.toString());
			contador ++ ;
		}
		arq.close();
	}

	private void algoritmo (Caverna[] nos) {

		No temp;
		No2 dist;
		while (heap[0] != null) {
			Caverna posicao = heap[0] ;
			temp = posicao.adj.inicio ;
			dist = posicao.dist.inicio ;
			posicao.marcado = false ;
			remocao(heap);
			while (temp != null) {
				if (dist.dist + posicao.distancia < temp.posicao.distancia) {
					temp.posicao.distancia = dist.dist + posicao.distancia ;
					temp.posicao.pontosVida = posicao.pontosVida - temp.posicao.pontosPerdidos ;
					if (temp.posicao.marcado == false) {
						inserir(heap,temp.posicao);
						temp.posicao.marcado = true ;
					}
				}
				else if (dist.dist + posicao.distancia == temp.posicao.distancia) {
					if (temp.posicao.pontosVida < posicao.pontosVida - temp.posicao.pontosPerdidos) {
						temp.posicao.pontosVida = posicao.pontosVida - temp.posicao.pontosPerdidos ;
					}
				}
				temp = temp.next ;
				dist = dist.next ;
			}
		}
	}

	public  void construirHeap (Caverna[] processos, int tam) {

		for (int i = tam/2 -1 ; i >= 0 ; i--) {
			heapify (processos,i,tam) ;
		}
	}
	public   void heapify(Caverna[] processos, int i,int tam) {
		int maior = 0 ;
		if (2*i + 1 < tam) {
			if (2* i + 2 < tam && compareTo(processos[2*i +2],processos[2*i+1]) > 0) {
				maior = 2*i + 2 ;
			}
			else {
				maior = 2*i + 1 ;
			}
		}
		if (maior != 0 && compareTo(processos[i],processos[maior])< 0){
			swap (processos,i,maior);
			heapify(processos,maior,tam);
		}
	}

	public void remocao (Caverna[] processos) {
		processos[0] = processos[numeroElementos - 1 ];
		processos[numeroElementos -1] = null ;
		heapify(processos,0,numeroElementos-1);
		numeroElementos -- ;

	}
	public void inserir (Caverna[] processos,Caverna processo) {
		processos[numeroElementos] = processo ;
		heapifySubindo (processos,numeroElementos);
		numeroElementos ++ ;
	}
	public void heapifySubindo (Caverna[] processos, int i) {
		if (i != 0 && compareTo(processos[i],processos[(i-1)/2]) > 0 ) {
			swap(processos,i,(i-1)/2) ;
			heapifySubindo(processos,(i-1)/2);
		}
	}
	public   void swap (Caverna [] processos,int i,int j){
		Caverna  temp = processos[i] ;
		processos[i] = processos[j];
		processos[j] = temp ;
	}

	public  int compareTo(Caverna a, Caverna b) {
		if (a.distancia >= b.distancia) {
			return -1 ;
		}
		else  {
			return 1 ;
		}
	}

	public static void main (String [] args) {
		new L3QD ();
	}
}