#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
<< ": "; \
dbgh(__VA_ARGS__)
#else
#define cerr \
if (false) \
cerr
#define dbg(...)
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))
template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
struct ST {
int n;
vector<vector<T>> v;
ST() {}
ST(const vector<T>& arr) : n(sz(arr)), v(__lg(n) + 1, vector<T>(n)) {
v[0] = arr;
for (int i = 1; i <= __lg(n); i++) {
for (int j = 0; j + (1 << i) <= n; j++) {
v[i][j] = min(v[i - 1][j], v[i - 1][j + (1 << (i - 1))]);
}
}
}
T query(int l, int r) const {
int x = __lg(r - l);
return min(v[x][l], v[x][r - (1 << x)]);
}
};
template <typename Cb>
struct KeyCmp {
Cb cb;
KeyCmp(Cb cb) : cb(cb) {}
template <typename T>
bool operator()(const T& a, const T& b) const {
return cb(a) < cb(b);
}
};
struct Dijkstra {
vector<vector<pair<int, long>>> graph;
Dijkstra() {}
int new_node() {
graph.emplace_back();
return sz(graph) - 1;
}
vector<int> new_node(int n) {
vector<int> arr;
for (int i = 0; i < n; i++) {
arr.push_back(new_node());
}
return arr;
}
void add_edge(int u, int v, long w) {
graph[u].emplace_back(v, w);
}
vector<long> query(int src) const {
vector<long> dist(sz(graph), 1e18);
min_pq<pair<long, int>> pq;
auto push = [&](int u, long d) -> void {
if (d >= dist[u]) {
return;
}
dist[u] = d;
pq.emplace(d, u);
};
push(src, 0);
while (sz(pq)) {
auto [d, u] = pq.top();
pq.pop();
if (dist[u] != d) {
continue;
}
for (auto& [v, w] : graph[u]) {
push(v, d + w);
}
}
return dist;
}
};
struct Tree {
int n;
vector<int> depth, tin, tout, ord;
vector<vector<int>> graph;
ST<int> st_ord;
Tree(int n, int root, const vector<pair<int, int>>& edges)
: n(n), depth(n), tin(n), tout(n), graph(n) {
for (auto& [u, v] : edges) {
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(root, -1, 0);
vector<int> stv;
for (auto& a : ord) {
stv.push_back(tin[a]);
}
st_ord = stv;
}
int lca(int u, int v) const {
if (tin[u] > tin[v]) {
swap(u, v);
}
return ord[st_ord.query(tin[u], tout[v])];
}
pair<vector<int>, vector<pair<int, int>>> virtual_tree(vector<int> nodes) {
sort(begin(nodes), end(nodes),
KeyCmp([&](int u) -> int { return tin[u]; }));
vector<int> anodes = nodes;
for (int i = 0; i < sz(nodes) - 1; i++) {
anodes.push_back(lca(nodes[i], nodes[i + 1]));
}
sort(begin(anodes), end(anodes),
KeyCmp([&](int u) -> int { return tin[u]; }));
anodes.erase(unique(begin(anodes), end(anodes)), anodes.end());
vector<int> st;
vector<pair<int, int>> edges;
for (auto& a : anodes) {
while (sz(st) && tout[st.back()] <= tin[a]) {
st.pop_back();
}
if (sz(st)) {
edges.emplace_back(st.back(), a);
}
st.push_back(a);
}
return {anodes, edges};
}
void dfs(int u, int p, int d) {
tin[u] = sz(ord);
depth[u] = d;
ord.push_back(u);
for (auto& v : graph[u]) {
if (v == p) {
continue;
}
dfs(v, u, d + 1);
ord.push_back(u);
}
tout[u] = sz(ord);
}
};
constexpr int maxn = 5e4 + 5;
// nodes - (u, depth, in, out)
// edges - (par, child)
void construct_tree(Dijkstra& graph,
vector<array<int, 4>> nodes,
vector<pair<int, int>> edges) {
static int nmap[maxn];
int n = sz(nodes);
for (int i = 0; i < n; i++) {
nmap[nodes[i][0]] = i;
}
vector<int> tup = graph.new_node(n), tdown = graph.new_node(n);
for (auto& [u, v] : edges) {
graph.add_edge(tup[nmap[v]], tup[nmap[u]], 0);
graph.add_edge(tdown[nmap[u]], tdown[nmap[v]], 0);
}
for (int i = 0; i < n; i++) {
graph.add_edge(nodes[i][2], tup[i], 0);
graph.add_edge(tdown[i], nodes[i][3], 0);
}
for (int i = 0; i < n; i++) {
graph.add_edge(nodes[i][2], tdown[i], nodes[i][1]);
graph.add_edge(tup[i], nodes[i][3], nodes[i][1]);
}
map<int, vector<int>> mch;
for (auto& [u, v] : edges) {
mch[u].push_back(v);
}
for (auto& [u, ch] : mch) {
int m = sz(ch);
vector<int> pref = graph.new_node(m), suff = graph.new_node(m);
for (int i = 0; i < m; i++) {
graph.add_edge(pref[i], tdown[nmap[ch[i]]], 0);
graph.add_edge(suff[i], tdown[nmap[ch[i]]], 0);
}
for (int i = 0; i < m - 1; i++) {
graph.add_edge(pref[i + 1], pref[i], 0);
graph.add_edge(suff[i], suff[i + 1], 0);
}
for (int i = 0; i < m; i++) {
if (i) {
graph.add_edge(tup[nmap[ch[i]]], pref[i - 1],
nodes[nmap[u]][1]);
}
if (i + 1 < m) {
graph.add_edge(tup[nmap[ch[i]]], suff[i + 1],
nodes[nmap[u]][1]);
}
}
}
}
void solve() {
int n, m, kv;
cin >> n >> m >> kv;
int edges[m][4];
for (auto& [u, v, w, t] : edges) {
cin >> u >> v >> w >> t;
u--;
v--;
t--;
}
vector<pair<int, int>> trie_edges(kv - 1);
for (auto& [u, v] : trie_edges) {
int _w;
cin >> u >> v >> _w;
u--;
v--;
}
Tree trie(kv, 0, trie_edges);
Dijkstra graph;
vector<int> reqs[n];
map<int, int> nodes[n][2];
for (auto& [u, v, w, t] : edges) {
reqs[u].push_back(t);
reqs[v].push_back(t);
}
for (int i = 0; i < n; i++) {
auto [anodes, tedges] = trie.virtual_tree(reqs[i]);
vector<array<int, 4>> cnodes;
for (auto& a : anodes) {
cnodes.push_back({a, trie.depth[a],
nodes[i][0][a] = graph.new_node(),
nodes[i][1][a] = graph.new_node()});
}
construct_tree(graph, cnodes, tedges);
}
for (auto& [u, v, w, t] : edges) {
graph.add_edge(nodes[u][1][t], nodes[v][0][t], w);
}
int src = graph.new_node();
for (auto& [_k, v] : nodes[0][1]) {
graph.add_edge(src, v, 0);
}
vector<long> dist = graph.query(src);
long ans[n];
memset(ans, 0x3f, sizeof(ans));
for (int i = 0; i < n; i++) {
for (auto& [_k, v] : nodes[i][0]) {
ans[i] = min(ans[i], dist[v]);
}
}
for (int i = 1; i < n; i++) {
cout << ans[i] << endl;
}
}
int main() {
cin.tie(nullptr);
cin.exceptions(ios::failbit);
ios_base::sync_with_stdio(false);
int tcs;
cin >> tcs;
while (tcs--) {
solve();
}
}