#include<stdio.h>
#include<algorithm>
#define Nmax 152
#define Kmax 12002
#define Tmax 3502
using namespace std;
int n,m,k,p;
int d[Nmax][Tmax];

struct graf
{
    int v,c;
    graf *adr;
};
graf *g[Nmax];

void graf_add(int v1,int v2,int c)
{
    graf *p;
    p=new graf;
    p->v=v2;
    p->c=c;
    p->adr=g[v1];
    g[v1]=p;
}

struct crima
{
    int v,t,c;
};
crima a[Kmax];

int cmp(crima a,crima b)
{
    if(a.c<b.c)
        return 1;
    return 0;
}

void citire()
{
    int i,x,y,c;
    scanf("%d %d %d %d",&n,&m,&k,&p);
    for(i=1;i<=m;++i)
    {
        scanf("%d %d %d",&x,&y,&c);
        graf_add(x,y,c);
        graf_add(y,x,c);
    }
    for(i=1;i<=k;++i)
    {
        scanf("%d %d %d",&x,&y,&c);
        a[i].v=x;
        a[i].t=y;
        a[i].c=c;
    }
    sort(a+1,a+k+1,cmp);
}

void parc()
{
    int i;
    for(i=1;i<=k;++i)
    {

    }
}

void rezolv()
{
    int i,x,t;
    parc();
    for(i=1;i<=p;++i)
    {
        scanf("%d %d",&x,&t);
        s=0;
    }
}

int main()
{
    freopen("amenzi.in","r",stdin);
  //  freopen("amenzi.out","w",stdout);
    citire();
    fclose(stdin);
    fclose(stdout);
    return 0;
}