// Skyqwq
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> void inline read(T &x) {
	x = 0; int f = 1; char s = getchar();
	while (s < '0' || s > '9') { if (s == '-') { f = -1; } s = getchar(); }
	while (s >= '0' && s <= '9') x = x * 10 + (s ^ 48), s = getchar();
	x *= f;
}

template <typename T> bool inline chkMin(T &x, T y) { return y < x ? x = y, 1 : 0; }
template <typename T> bool inline chkMax(T &x, T y) { return y > x ? x = y, 1 : 0; }

const int N = 5e4 + 5, S = 2e4 + 5, M = N + S * 8 + S * 2;

int n, m, k, A[N], B[N], C[N], D[N], fa[S], sz[S], dep[S], L[S], R[S], pre[S], idx, rt[S];

vector<PII> e[S];


int dfn[N], dfncnt;

void dfs1(int u) {
	sz[u] = 1;
	dfn[u] = ++dfncnt;
	pre[dfn[u]] = u;
	L[u] = dfn[u];
	for (PII o: e[u]) {
		int v = o.fi;
		if (v == fa[u]) continue;
		fa[v] = u;
		dep[v] = dep[u] + 1;
		dfs1(v);
		sz[u] += sz[v];
	}
	R[u] = dfncnt;
}



LL d[M], ans[N];

bool vis[M];

vector<PII> g[M];

int id;

struct T{
	int l, r;
	int w[2];
	// 0: in
	// 1: out
} t[N * 17 * 2];


void add(int x, int y, int z) {
	g[x].pb(mp(y, z));
}

void inline clr() {
	dfncnt = 0;
	for (int i = 1; i <= k; i++) rt[i] = fa[i] = sz[i] = dep[i] = dfn[i] = 0, e[i].clear();
	for (int i = 1; i <= idx; i++) vis[i] = d[i] = 0;
	for (int i = 1; i <= idx; i++) g[i].clear();
	for (int i = 1; i <= id; i++) {
		t[i].l = t[i].r = t[i].w[0] = t[i].w[1] = 0;
	}
	id = 0;
}


#define ls t[p].l
#define rs t[p].r


void ins(int &p, int l, int r, int x, int o, int u, int k, int w) {
	if (!p) p = ++id;
	if (l == r) {
		if (!t[p].w[o]) {
			t[p].w[o] = ++idx;
			if (t[p].w[0] && t[p].w[1])
				add(t[p].w[1], t[p].w[0], w);
		}
		if (!o) add(t[p].w[o], u, k);
		else add(u, t[p].w[o], k);
		return;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) ins(ls, l, mid, x, o, u, k, w);
	else ins(rs, mid + 1, r, x, o, u, k, w);
}

void mg(int &p, int q, int l, int r, int w) {
	if (!q) return;
	if (!p) { p = q; return ;}
	if (l == r) {
		if (t[p].w[1] && t[q].w[0]) add(t[p].w[1], t[q].w[0], w);
		if (t[q].w[1] && t[p].w[0]) add(t[q].w[1], t[p].w[0], w);
		for (int i = 0; i < 2; i++) {
			if (t[p].w[i] && t[q].w[i]) {
				++idx;
				if (i == 1) add(t[p].w[i], idx, 0), add(t[q].w[i], idx, 0);
				else add(idx, t[p].w[i], 0), add(idx, t[q].w[i], 0);
				t[p].w[i] = idx;
			} else t[p].w[i] = t[p].w[i] | t[q].w[i];
		}
		return;
	} 
	int mid = (l + r) >> 1;
	mg(ls, t[q].l, l, mid, w);
	mg(rs, t[q].r, mid + 1, r, w);
}

void dfs2(int u) {
	for (PII o: e[u]) {
		int v = o.fi;
		if (v == fa[u]) continue;
		dfs2(v);
		mg(rt[u], rt[v], 1, n, dep[u]);
	}
}

typedef pair<LL, int> PLI;

priority_queue<PLI, vector<PLI>, greater<PLI> > q;

void dij() {
	memset(d, 0x3f, sizeof d);
	memset(ans, 0x3f, sizeof ans);
	for (int i = 1; i <= m; i++)
		if (A[i] == 1) d[i] = C[i], q.push(mp(d[i], i));
	while (!q.empty()) {
		int u = q.top().se; q.pop();
		if (vis[u]) continue;
		vis[u] = 1; 
		if (u <= m) chkMin(ans[B[u]], d[u]);
		for (PII o: g[u]) {
			int v = o.fi, w = o.se;
			if (d[u] + w < d[v]) {
				d[v] = d[u] + w;
				q.push(mp(d[v], v));
 			}
		}
	}
}

int main() {
	//freopen("A.in", "r", stdin);
	int T; read(T);
	while (T--) {
		read(n), read(m), read(k);
		for (int i = 1; i <= m; i++) {
			read(A[i]), read(B[i]), read(C[i]), read(D[i]);
		}
		for (int i = 1; i < k; i++) {
			int u, v, w; 
			read(u), read(v), read(w);
			e[u].pb(mp(v, w)), e[v].pb(mp(u, w));
		}
		dfs1(1);
		idx = m;
		for (int i = 1; i <= m; i++) {
			ins(rt[D[i]], 1, n, B[i], 1, i, 0, dep[D[i]]);
			ins(rt[D[i]], 1, n, A[i], 0, i, C[i], dep[D[i]]);
		}
		dfs2(1);
		dij();
		for (int i = 2; i <= n; i++) printf("%lld\n", ans[i]);
		clr();
	}
	return 0;
}