package lista3;
import Arquivo;

public class L3QD {
	Arquivo arquivo;
	int elementos = 0 ;
	Caverna[] heap ;

	public L3QD () {
		arquivo = new Arquivo("L3QD.in","L3QD.out");
		int caso = 1 ;
		while (!arquivo.isEndOfFile()) {
			int numCav = arquivo.readInt () ;
			int tuneis = arquivo.readInt();
			int hp = arquivo.readInt();
			int mosntros = arquivo.readInt();
			arquivo.print("Caso #");
			arquivo.println(caso);
			Caverna[] cavernas = new Caverna[numCav];

             for (int i = 0; i < numCav; i++) {
            	 cavernas[i] = new Caverna() ;
            	 cavernas[i].numero = i ;

             }
			for (int j = 0 ; j < tuneis ; j++) {
				int entrada = arquivo.readInt();
				int saida = arquivo.readInt();
				cavernas[entrada].adjacencia.inserir(new No(cavernas[saida]));
				cavernas[saida].adjacencia.inserir(new No(cavernas[entrada]));
				int tam = arquivo.readInt();
				cavernas[entrada].dist.inserir(tam);
				cavernas[saida].dist.inserir(tam);
			}
			for (int k = 0; k < mosntros; k++) {
				int cave = arquivo.readInt();
				int pontos = arquivo.readInt();
				cavernas[cave].perda += pontos ;
			}
			heap = new Caverna[numCav];
			cavernas[0].distancia = 0 ;
			cavernas[0].life = hp - cavernas[0].perda ;
			inserir(heap,cavernas[0]);
			rotina(cavernas);

			for (int i = 0; i < numCav; i++) {
				if (cavernas[i].life <= 0 || cavernas[i].distancia == Integer.MAX_VALUE ) {
					arquivo.println("Morte certa!");
				}
				else {
					arquivo.print(cavernas[i].distancia);
					arquivo.print(" ");
					arquivo.println(cavernas[i].life);
				}
			}
			arquivo.println("");
			elementos = 0;
			caso ++ ;
		}
		arquivo.close();
	}

	private void rotina (Caverna[] nos) {
		No temp;
		No2 temp2;

		while (heap[0] != null) {
			Caverna posicao = heap[0] ;
			temp = posicao.adjacencia.inicio ;
			temp2 = posicao.dist.inicio ;
			posicao.marcado = false ;
			remover(heap);

			while (temp != null) {
				int difenca = posicao.life - temp.posicao.perda;
				if (temp2.dist + posicao.distancia < temp.posicao.distancia && difenca > 0) {
					temp.posicao.distancia = temp2.dist + posicao.distancia ;
					temp.posicao.life = posicao.life - temp.posicao.perda ;
					if (temp.posicao.marcado ==  false ) {
						inserir(heap,temp.posicao);
						temp.posicao.marcado = true ;
					}
				}
				else if (temp2.dist + posicao.distancia == temp.posicao.distancia && difenca > 0) {
					if (temp.posicao.life < posicao.life - temp.posicao.perda) {
						temp.posicao.life = posicao.life - temp.posicao.perda ;
						if (temp.posicao.marcado == false ) {
							inserir(heap,temp.posicao);
							temp.posicao.marcado = true ;
						}
					}
				}
				temp = temp.next ;
				temp2 = temp2.next ;
			}
		}
	}

	public  void heap (Caverna[] processos, int tamanho) {

		for (int i = tamanho/2 -1 ; i >= 0 ; i--) {
			heapify (processos,i,tamanho) ;
		}
	}

	public void inserir (Caverna[] processos,Caverna processo) {
		processos[elementos] = processo ;
		heapifyBottomUp (processos,elementos);
		elementos = elementos + 1; ;
	}

	public   void heapify(Caverna[] processos, int i,int tamanho) {
		int maior = 0 ;
		if (2*i + 1 < tamanho) {
			if (2* i + 2 < tamanho && 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){
			troca (processos,i,maior);
			heapify(processos,maior,tamanho);
		}
	}

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

	}
	public void heapifyBottomUp (Caverna[] processos, int i) {
		if (i != 0 && compareTo(processos[i],processos[(i-1)/2]) > 0 ) {
			troca(processos,i,(i-1)/2) ;
			heapifyBottomUp(processos,(i-1)/2);
		}
	}
	public void troca (Caverna [] processos,int i,int j){
		Caverna  temp = processos[i] ;
		processos[i] = processos[j];
		processos[j] = temp ;
	}

	public int compareTo(Caverna c1, Caverna c2) {
		int retorno = 0;
		if (c1.distancia > c2.distancia) {
			retorno = -1 ;
		}
		else if (c1.distancia == c2.distancia)  {
			if (c1.life >= c2.life) {
				retorno = -1 ;
			}
			else {
				retorno = 1;
			}
		}
		else {
			retorno = 1;
		}
		return retorno;
	}

	public static void main (String [] args) {
		new L3QD ();
	}
}
//FIM DA CLASSE PRINCIPAL

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

}
//FIM DA CLASSE NO

class Caverna {
	int distancia = Integer.MAX_VALUE ;
	int numero ;
	int perda = 0;
	int life ;
	Lista2 dist = new Lista2 () ;
	Lista adjacencia = new Lista () ;
	boolean marcado = false ;
}
//FIM DA CLASSE CAVERNA

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 ;
		}
	}
}
//FIM DA CLASSE LISTA

class No2 {
	int dist ;
	No2 next ;
	public No2(int dist) {
		this.dist = dist ;
	}
}
//FIM DA CLASSE NO2

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 ;
		}
	}
}
//FIM DA CLASSE LISTA2

class Grafo {
	Caverna inicio ;
	int fim ;
}
//FIM DA CLASSE GRAFO