#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <queue>
using namespace std;
 
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
    if(Head == Tail) {
        int l = fread(buffer, 1, BufferSize, stdin);
        Tail = (Head = buffer) + l;
    }
    return *Head++;
}
int read() {
    int x = 0, f = 1; char c = Getchar();
    while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
    while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
    return x * f;
}
 
#define maxn 100010
#define maxnode 1000010
#define maxm 6000380
#define maxlog 17
#define ool (1ll << 60)
#define LL long long
 
namespace NG {
    int ToT, val[maxnode];
     
    int iRt[maxn], oRt[maxn];
    struct Seg_info {
        int l, r, lc, rc;
        Seg_info() {}
        Seg_info(int _1, int _2, int _3, int _4): l(_1), r(_2), lc(_3), rc(_4) {}
    } info[maxnode];
     
    int m, head[maxnode], nxt[maxm], to[maxm], dist[maxm];
    void init() {
        ToT = 0;
        memset(val, 0, sizeof(val));
        m = 0; memset(head, 0, sizeof(head));
        return ;
    }
     
    void AddEdge(int a, int b, int c) {
//      printf("NG::AddEdge(%d -> %d : %d)\n", a, b, c);
        to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m;
        return ;
    }
     
    int iseg_node(int o, int pos) {
        if(info[o].l == info[o].r) return o;
        int mid = info[o].l + info[o].r >> 1;
        if(pos <= mid) {
            if(!info[o].lc) {
                info[o].lc = ++ToT;
                info[info[o].lc] = Seg_info(info[o].l, mid, 0, 0);
                AddEdge(info[o].lc, o, 0);
            }
            return iseg_node(info[o].lc, pos);
        }
        if(!info[o].rc) {
            info[o].rc = ++ToT;
            info[info[o].rc] = Seg_info(mid + 1, info[o].r, 0, 0);
            AddEdge(info[o].rc, o, 0);
        }
        return iseg_node(info[o].rc, pos);
    }
    int oseg_node(int o, int pos) {
        if(info[o].l == info[o].r) return o;
        int mid = info[o].l + info[o].r >> 1;
        if(pos <= mid) {
            if(!info[o].lc) {
                info[o].lc = ++ToT;
                info[info[o].lc] = Seg_info(info[o].l, mid, 0, 0);
                AddEdge(o, info[o].lc, 0);
            }
            return oseg_node(info[o].lc, pos);
        }
        if(!info[o].rc) {
            info[o].rc = ++ToT;
            info[info[o].rc] = Seg_info(mid + 1, info[o].r, 0, 0);
            AddEdge(o, info[o].rc, 0);
        }
        return oseg_node(info[o].rc, pos);
    }
     
    int cIntv, Intv[maxn];
    void getintv(int o, int ql, int qr) {
        if(!o) return ;
        if(ql <= info[o].l && info[o].r <= qr) Intv[++cIntv] = o;
        else {
            int mid = info[o].l + info[o].r >> 1;
            if(ql <= mid) getintv(info[o].lc, ql, qr);
            if(qr > mid) getintv(info[o].rc, ql, qr);
        }
        return ;
    }
    void GetIntv(int o, int ql, int qr) {
        cIntv = 0;
        if(ql > qr) return ;
        getintv(o, ql, qr);
        return ;
    }
     
    struct Node {
        int u; LL d;
        Node() {}
        Node(int _, LL __): u(_), d(__) {}
        bool operator < (const Node& t) const { return d > t.d; }
    };
    priority_queue <Node> Q;
    bool vis[maxnode];
    LL d[maxnode];
    void ShortPath(int s) {
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= ToT; i++) d[i] = ool;
        d[s] = 0; Q.push(Node(s, 0));
        while(!Q.empty()) {
            int u = Q.top().u; Q.pop();
//          printf("(u)%d ", u);
            if(vis[u]) continue;
            vis[u] = 1;
            for(int e = head[u]; e; e = nxt[e]) if(d[to[e]] > d[u] + dist[e] + val[to[e]]) {
                d[to[e]] = d[u] + dist[e] + val[to[e]];
                if(!vis[to[e]]) Q.push(Node(to[e], d[to[e]]));
            }
        }
        return ;
    }
}
 
struct Edge {
    int from, to, dist, tnode;
    Edge() {}
    Edge(int _1, int _2, int _3, int _4): from(_1), to(_2), dist(_3), tnode(_4) {}
} es[maxn];
struct Graph {
    int m, hto[maxn], nto[maxn], hfr[maxn], nfr[maxn];
     
    void init() { m = 0; memset(hto, 0, sizeof(hto)); memset(hfr, 0, sizeof(hfr)); return ; }
     
    void AddEdge(int a, int b, int c, int d) {
        es[++m] = Edge(a, b, c, d);
        nto[m] = hto[a]; hto[a] = m;
        nfr[m] = hfr[b]; hfr[b] = m;
        return ;
    }
} G;
 
struct Tree {
    int n, m, head[maxn], nxt[maxn], to[maxn];
    int dep[maxn], Log[maxn<<1], mnp[maxlog][maxn<<1], pos[maxn], clo;
     
    void init() { m = 0; memset(head, 0, sizeof(head)); clo = 0; return ; }
     
    void AddEdge(int a, int b) {
        to[++m] = b; nxt[m] = head[a]; head[a] = m;
        return ;
    }
     
    void build(int u) {
        mnp[0][++clo] = u; pos[u] = clo;
        for(int e = head[u]; e; e = nxt[e]) {
            dep[to[e]] = dep[u] + 1;
            build(to[e]);
            mnp[0][++clo] = u;
        }
        return ;
    }
    void rmq_init() {
        Log[1] = 0;
        for(int i = 2; i <= clo; i++) Log[i] = Log[i>>1] + 1;
        for(int j = 1; (1 << j) <= clo; j++)
            for(int i = 1; i + (1 << j) - 1 <= clo; i++) {
                int a = mnp[j-1][i], b = mnp[j-1][i+(1<<j-1)];
                mnp[j][i] = dep[a] < dep[b] ? a : b;
            }
        return ;
    }
    int lca(int a, int b) {
        int l = pos[a], r = pos[b];
        if(l > r) swap(l, r);
        int t = Log[r-l+1];
        a = mnp[t][l]; b = mnp[t][r-(1<<t)+1];
        return dep[a] < dep[b] ? a : b;
    }
    int cdist(int a, int b) {
        return dep[a] + dep[b] - (dep[lca(a,b)] << 1);
    }
} tree;
 
bool cmp(int a, int b) { return tree.pos[a] < tree.pos[b]; }
struct VTree {
    int n, m, head[maxn], nxt[maxn], to[maxn], dist[maxn];
    int nodes[maxn], iN[maxn], ci, oN[maxn], co;
    int dl[maxn], dr[maxn], clo;
    int iRt, oRt, buff[maxn], cbuff;
     
    void init() {
        m = 0; memset(head, 0, sizeof(head));
        return ;
    }
     
    void AddEdge(int a, int b, int c) {
        to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m;
        return ;
    }
     
    void build(int u) {
        dl[u] = ++clo;
        for(int e = head[u]; e; e = nxt[e]) build(to[e]);
        dr[u] = clo;
        return ;
    }
     
    void AddEdges(int u) {
//      printf("AddEdgessssssssss(%d) [%d, %d] %d\n", u, dl[u], dr[u], NG::m);
        NG::GetIntv(iRt, dl[u], dl[u]);
        if(NG::cIntv) {
            int x = NG::Intv[1];
            NG::GetIntv(oRt, dl[u], dr[u]);
//          printf("[%d, %d]: %d\n", dl[u], dr[u], NG::cIntv);
            if(NG::cIntv) {
                for(int i = 1; i <= NG::cIntv; i++) {
                    NG::AddEdge(x, NG::Intv[i], tree.dep[u]);
//                  printf("HERE@@@@@@@ %d -> %d : %d\n", x, NG::Intv[i], tree.dep[u]);
                }
            }
        }
        NG::GetIntv(oRt, dl[u], dl[u]);
        if(NG::cIntv) {
            int x = NG::Intv[1];
            NG::GetIntv(iRt, dl[u] + 1, dr[u]);
            if(NG::cIntv) {
                for(int i = 1; i <= NG::cIntv; i++) {
                    NG::AddEdge(NG::Intv[i], x, tree.dep[u]);
//                  printf("HERE@@@@@@@ %d -> %d : %d | we are here %d\n", NG::Intv[i], x, tree.dep[u], u);
                }
            }
        }
        for(int e = head[u]; e; e = nxt[e]) {
            NG::GetIntv(iRt, dl[to[e]], dr[to[e]]);
            if(NG::cIntv) {
                cbuff = NG::cIntv;
                for(int i = 1; i <= cbuff; i++) buff[i] = NG::Intv[i];
            }
            else continue;
            int newnode = 0;
            NG::GetIntv(oRt, dl[u] + 1, dl[to[e]] - 1);
            if(NG::cIntv) {
                newnode = ++NG::ToT;
                for(int i = 1; i <= cbuff; i++) NG::AddEdge(buff[i], newnode, tree.dep[u]);
                for(int i = 1; i <= NG::cIntv; i++) NG::AddEdge(newnode, NG::Intv[i], 0);
            }
            NG::GetIntv(oRt, dr[to[e]] + 1, dr[u]);
            if(NG::cIntv) {
                if(newnode) for(int i = 1; i <= NG::cIntv; i++) NG::AddEdge(newnode, NG::Intv[i], 0);
                else {
                    newnode = ++NG::ToT;
                    for(int i = 1; i <= cbuff; i++) NG::AddEdge(buff[i], newnode, tree.dep[u]);
                    for(int i = 1; i <= NG::cIntv; i++) NG::AddEdge(newnode, NG::Intv[i], 0);
                }
            }
        }
        /*printf("(u)%d: ", u);
        for(int e = head[u]; e; e = nxt[e]) printf("%d ", to[e]);
        printf("to[e] ends\n");*/
        for(int e = head[u]; e; e = nxt[e]) AddEdges(to[e]);
//      printf("return to %d [%d, %d]\n", u, dl[u], dr[u]);
        return ;
    }
     
    void G_build(int u) {
        init();
        n = ci = co = 0;
        for(int e = G.hfr[u]; e; e = G.nfr[e]) iN[++ci] = e, nodes[++n] = es[e].tnode;
        for(int e = G.hto[u]; e; e = G.nto[e]) oN[++co] = e, nodes[++n] = es[e].tnode;
        if(!ci || !co) return ;
        sort(nodes + 1, nodes + n + 1, cmp);
        int t = n;
        for(int i = 1; i < t; i++) nodes[++n] = tree.lca(nodes[i], nodes[i+1]);
        sort(nodes + 1, nodes + n + 1, cmp);
        n = unique(nodes + 1, nodes + n + 1) - nodes - 1;
        for(int i = 1; i < n; i++) {
            int a = nodes[i], b = nodes[i+1], c = tree.lca(a, b);
            AddEdge(c, b, tree.cdist(c, b));
        }
        clo = 0;
        build(nodes[1]);
        NG::info[iRt = NG::iRt[u] = ++NG::ToT] = NG::Seg_info(1, clo, 0, 0);
        NG::info[oRt = NG::oRt[u] = ++NG::ToT] = NG::Seg_info(1, clo, 0, 0);
//      printf("G_build(%d) %d %d %d\n", u, n, clo, nodes[1]);
        for(int i = 1; i <= ci; i++) {
            int u = NG::iseg_node(iRt, dl[es[iN[i]].tnode]);
            NG::AddEdge(iN[i], u, 0);
        }
        for(int i = 1; i <= co; i++) {
            int u = NG::oseg_node(oRt, dl[es[oN[i]].tnode]);
            NG::AddEdge(u, oN[i], 0);
        }
        AddEdges(nodes[1]);
        return ;
    }
} vtree;
 
LL Ans[maxn];
 
void work() {
    G.init(); tree.init();
     
    int n = read(), m = read(), k = read();
//  printf("%d %d %d\n", n, m, k);
    for(int i = 1; i <= m; i++) {
        int a = read(), b = read(), c = read(), d = read();
        G.AddEdge(a, b, c, d);
    }
     
    NG::init();
    NG::ToT = m;
    for(int i = 1; i <= G.m; i++) NG::val[i] = es[i].dist;
    int Start = ++NG::ToT;
    for(int e = G.hto[1]; e; e = G.nto[e]) NG::AddEdge(Start, e, 0);
     
    for(int i = 1; i < k; i++) {
        int a = read(), b = read(); read();
        tree.AddEdge(a, b);
    }
    tree.build(1); tree.rmq_init();
     
    for(int i = 1; i <= n; i++) vtree.G_build(i);
     
//  printf("ToT: %d %d\n", NG::ToT, NG::m);
    NG::ShortPath(Start);
    for(int i = 1; i <= n; i++) Ans[i] = ool;
    for(int i = 1; i <= G.m; i++) Ans[es[i].to] = min(Ans[es[i].to], NG::d[i]);
     
    for(int i = 2; i <= n; i++) printf("%lld\n", Ans[i]);
     
    return ;
}
 
int main() {
    int T = read();
    while(T--) work();
     
    return 0;
}