#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define inf 1<<20
#define nmax 155
#define first x
#define second y

ifstream f("amenzi.in");
ofstream g("amenzi.out");

/*struct str
{
    int vecin,cost;
};*/

struct str2
{
    int moment,val;
};

/*vector<str>Q[nmax];*/
vector<str2>amenzi[nmax];
vector<pair<int,int>>query;

int n,m,k,p,cost[nmax][nmax],bestcost[nmax][nmax];

void read()
{
    f>>n>>m>>k>>p;
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=n; ++j)
            bestcost[i][j]=cost[i][j]=inf;
    for (int i=1; i<=m; ++i)
    {
        int e1,e2,e3;
        f>>e1>>e2>>e3;
        cost[e1][e2]=cost[e2][e1]=e3;
        bestcost[e1][e2]=bestcost[e2][e1]=e3;
    }
    for (int i=1; i<=k; ++i)
    {
        int e1,e2,e3;
        f>>e1>>e2>>e3;
        amenzi[e1].push_back({e2,e3});
    }
    for (int i=1; i<=p; ++i)
    {
        int e1,e2;
        f>>e1>>e2;
        query.push_back({e1,e2});
    }
}

void floyd_warshall()
{
    for (int k=1; k<=n; ++k)/
        for (int i=1; i<=n; ++i)
            for (int j=1; j<=n; ++j)
                if (cost[i][j]!=inf)
                    bestcost[i][j]=bestcost[j][i]=min(bestcost[j][i],bestcost[i][k]+bestcost[k][j]+cost[i][j]);
}

void solve()
{
    floyd_warshall();
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=n;++j)
            g<<bestcost[i][j]<<' ';
        g<<'\n';
    }
}

int main()
{
    read();
    solve();
    return 0;
}