#include "bits/stdc++.h"
using namespace std;
struct Arista{
int u, v, ID_opuesto;
long long Capacidad, Flujo, Costo;
};
vector<Arista> Lista;
vector< vector<int> > Grafo;
vector<long long> Distancias, Potenciales;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, k;
long long r, t, DOS = 2222222222222222;
cin>>n>>m>>r>>t>>k;
//cerr<<t / r<<"\n\n";
Grafo.assign(n + m + 22, {});
Potenciales.assign(n + m + 22, 0);
Distancias.assign(n + m + 22, DOS);
int ID = 0;
for(int i = 0; i < k; i++){
int a, b;
cin>>a>>b;
a--;
b = b - 1 + n;
Grafo[a].push_back(ID);
Grafo[b].push_back(ID + 1);
Lista.push_back({a, b, ID + 1, 1, 0, 1});
Lista.push_back({b, a, ID, 0, 0, -1});
ID += 2;
}
for(int i = 0; i < n; i++){
Grafo[n + m + 2].push_back(ID);
Grafo[i].push_back(ID + 1);
Lista.push_back({n + m + 2, i, ID + 1, t / r, 0, 1});
Lista.push_back({i, n + m + 2, ID, 0, 0, -1});
ID += 2;
}
for(int i = n; i < n + m; i++){
Grafo[i].push_back(ID);
Grafo[n + m + 4].push_back(ID + 1);
Lista.push_back({i, n + m + 4, ID + 1, 1, 0, 1});
Lista.push_back({n + m + 4, i, ID, 0, 0, -1});
ID += 2;
}
long long Flujo_m_ximo = 0, Costo_m_nimo = 0;
while(1){
Distancias[n + m + 2] = 0;
priority_queue< pair<long long, int>, vector< pair<long long, int> >, greater< pair<long long, int> > > Cola;
Cola.push({0, n + m + 2});
vector< pair<int, int> > Ancestros(n + m + 22, {-2, -2});
vector<long long> Flujo_mandado(n + m + 22, 0);
Flujo_mandado[n + m + 2] = LLONG_MAX;
while(!Cola.empty()){
/*for(auto E: Distancias) cerr<<E<<" ";
cerr<<"\n";*/
for(auto E: Flujo_mandado) cerr<<E<<" ";
cerr<<"\n";
int Nodo = Cola.top().second;
Cola.pop();
for(auto E: Grafo[Nodo]){
auto Siguiente = Lista[E];
//cerr<<Nodo<<" "<<Siguiente.v<<" ";
if(Siguiente.Flujo >= Siguiente.Capacidad){
//cerr<<"No se puede pasar.\n";
continue;
}
long long Distancia = Distancias[Nodo] + Siguiente.Costo + Potenciales[Siguiente.v] - Potenciales[Nodo];
if(Distancia >= Distancias[Siguiente.v]){
//cerr<<Distancia<<" "<<Distancias[Siguiente.v]<<" Muy lejos.\n";
continue;
}
//cerr<<Nodo<<" "<<Siguiente.v<<" "<<Siguiente.Flujo<<" "<<Siguiente.Capacidad<<" "<<Distancia<<"\n";
Distancias[Siguiente.v] = Distancia;
Cola.push({Distancia, Siguiente.v});
Ancestros[Siguiente.v] = {Nodo, E};
Flujo_mandado[Siguiente.v] = Siguiente.Capacidad - Siguiente.Flujo;
}
}
//cerr<<"\n";
if(Flujo_mandado[n + m + 4] == 0) break;
for(int Nodo = n + m + 4; Nodo != n + m + 2; Nodo = Ancestros[Nodo].first){
cerr<<Nodo<<" ";
Flujo_mandado[n + m + 2] = min(Flujo_mandado[n + m + 2], Flujo_mandado[Nodo]);
}
cerr<<"\n";
Flujo_m_ximo += Flujo_mandado[n + m + 2];
for(int Nodo = n + m + 4; Nodo != n + m + 2; Nodo = Ancestros[Nodo].first){
Lista[Ancestros[Nodo].second].Flujo += Flujo_mandado[n + m + 2];
Lista[Lista[Ancestros[Nodo].second].ID_opuesto].Flujo -= Flujo_mandado[n + m + 2];
if(Ancestros[Nodo].first == n + m + 2){
Lista[Ancestros[Nodo].second].Costo += Flujo_mandado[n + m + 2];
Lista[Lista[Ancestros[Nodo].second].ID_opuesto].Costo -= Flujo_mandado[n + m + 2];
}
}
for(int i = 0; i < n + m + 22; i++){
if(Distancias[i] != DOS) Potenciales[i] += Distancias[i];
Distancias[i] = DOS;
cerr<<Potenciales[i]<<" ";
}
cerr<<"\n";
}
for(auto E: Lista) Costo_m_nimo += (E.Flujo * E.Flujo + E.Flujo) / 2;
cout<<Flujo_m_ximo<<" "<<Costo_m_nimo<<"\n";
for(int i = 0; i < n; i++){
long long Contador = 0;
for(auto E: Grafo[i]){
auto Siguiente = Lista[E];
if(Siguiente.Flujo != 1) continue;
cout<<i + 1<<" "<<Siguiente.v - n + 1<<" "<<Contador * r<<"\n";
Contador++;
}
}
return 0;
}
