#include <bits/stdc++.h>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("c.in", "r", stdin);
        freopen("c.out", "w", stdout);
    }
};
// Rhine_Lab Ptilopsis_w;

using ll = long long;
const int N = 50005;

struct edge { int to, cost, pos; };

int n, m, k;
vector<edge> ver[N];
unordered_map<ll, ll> dis;
unordered_set<ll> vis; 
vector<int> from[N];

ll id(int x, int y) { return (ll)k*x + y-1; }

namespace tree {
    const int LOG = 20;
    int dep[N];
    int f[N][LOG+1];
    int dfn[N], dft;
    vector<int> tr[N];
    void dfs(int x)
    {
        dfn[x] = ++dft;
        f[dft][0] = x;
        for(auto y : tr[x])
        {
            dep[y] = dep[x]+1;
            dfs(y);
            f[++dft][0] = x;
        }
    }
    int comp(int a, int b)
    {
        return dep[a] < dep[b] ? a : b;
    }
    void buildST()
    {
        for(int s = 1; s <= LOG; s++)
            for(int i = 1; i+(1<<s)-1 <= dft; i++)
                f[i][s] = comp(f[i][s-1], f[i+(1<<(s-1))][s-1]);
    }
    int query(int x, int y)
    {
        x = dfn[x], y = dfn[y];
        if(x > y) swap(x, y);
        int s = log2(y-x+1);
        return dep[comp(f[x][s], f[y-(1<<s)+1][s])];
    }
} using namespace tree;

void solve();
void clear();
void dijkstra(int s);

int main()
{
    int T; cin >> T;
    while(T --> 0) solve(), clear();
}

void solve()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        ver[a].push_back({b, c, d});
        from[b].push_back(d);
    }
    for(int i = 1; i <= k-1; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        tr[a].push_back(b);
    }
    
    tree::dfs(1);
    tree::buildST();
    
    dijkstra(1);
    
    for(int i = 2; i <= n; i++)
    {
        ll mn = LLONG_MAX;
        for(auto j : from[i])
            mn = min(mn, dis[id(i,j)]);
        cout << mn << "\n";
    }
}

void dijkstra(int s)
{
    using node = pair<ll, ll>; 
    priority_queue< node, vector<node>, greater<> > q;
    q.push({0, id(s,1)}); dis[id(s,1)] = 0;
    while(!q.empty())
    {
        auto a = q.top(); q.pop();
        if(vis.count(a.second)) continue;
        vis.insert(a.second);
        int x = a.second/k, pos = a.second%k;
        for(auto i : ver[x])
        {
            ll y = id(i.to, i.pos);
            ll cost = a.first + i.cost + tree::query(pos, i.pos);
            if(!dis.count(y) or dis[y] > cost)
            {
                dis[y] = cost;
                q.push({cost, y});
            }
        }
    }
}

void clear()
{
    dft = 0;
    // memset(f, 0, sizeof(f));
    // memset(dfn, 0, sizeof(dfn));
    // memset(dep, 0, sizeof(dep));
    for(auto &i : tr) i.clear();
    
    dis.clear(); vis.clear();
    for(auto &i : ver) i.clear();
    for(auto &i : from) i.clear();
}

/*
1
4 4 6
1 2 2 5
2 3 2 5
2 4 1 6
4 2 1 6
1 2 1
2 3 1
3 4 1
4 5 2
1 6 2

*/