#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define pir pair<pii,int>
#define fi first
#define se second
#define all(_a) _a.begin(), _a.end()
struct Node
{
    int to,c,len;
};
const int N=500010;
vector<Node>g[N];
set<array<int,3>> s[N];
pii dist[N];
int l[N],r[N],a[N],t[N],ft[N],se;
bool st[N]; int T;
////////////////////////////////////////////
struct node
{
    int l, r;
    int v;  // 区间[l, r]中的最大值
}tr[N * 4];

void pushup(int u)  // 由子节点的信息，来计算父节点的信息
{
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l == r) {
        tr[u].v=a[l];
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;   // 树中节点，已经被完全包含在[l, r]中了

    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    if (l <= mid) v = query(u << 1, l, r);
    if (r > mid) v = max(v, query(u << 1 | 1, l, r));

    return v;
}
////////////////////////////////////////
void dij(){
    dist[1].fi=0;
    priority_queue<pir,vector<pir>,greater<pir>>q;
    q.push({dist[1],1});
    while(q.size()){
        int u=q.top().se;
        q.pop();
        if(st[u])continue;
        st[u]=true;
        for(auto ne:g[u]){
            int v=ne.to;
            int c=ne.c;
            int len=ne.len;
            if(t[dist[u].fi]==c&&len<=dist[u].se){
                pii p={dist[u].fi,dist[u].se-len};
                if(p<dist[v]){
                    dist[v]=p;
                    q.push({dist[v],v});
                }

                continue;
            }
            if(s[c].empty())continue;
            auto it=s[c].lower_bound({dist[u].fi,INF,INF});
            if(it==s[c].end())continue;
            int L=l[c]+(*it)[1],R=r[c];
            if(query(1,L,R)<len)continue;
            {
                int l=L,r=R;

                while(l<r){
                    int mid=l+r>>1;
                    if(query(1,L,mid)>=len)r=mid;
                    else l=mid+1;
                }
                pii p={ft[r],query(1,L,r)-len};
                if(p<dist[v]){
                    dist[v]=p;
                    q.push({dist[v],v});
                }
            }
        }

    }
}
////////////////////////////////////////
void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    ///////
    vector<Node>add;
    vector<pii>addk;

    /////
    for(int i=1;i<=n;i++){
        dist[i].fi=INF;
        st[i]=false;
        g[i].clear();
        
    }
    for(int i=1;i<=m;i++){
        s[i].clear();
        l[i]=r[i]=0;
    }
    for(int i=1;i<=m;i++){
        int x,y,c,len;
        cin>>x>>y>>c>>len;
        add.push_back({x,y,len});
        g[x].push_back({y,c,len});
        g[y].push_back({x,c,len});
    }
    for(int i=1;i<=k;i++){
        int c,len;
        cin>>c>>len;
        addk.push_back({c,len});
        s[c].insert({i,(int)s[c].size(),len});
        t[i]=c;
    }
    int len=0;
    for(int i=1;i<=m;i++){
        if(s[i].empty())continue;
        l[i]=len+1;
        r[i]=len+s[i].size();
        for(auto v:s[i]){
            int x=v[2];
            a[++len]=x;
            ft[len]=v[0];
        }
    }
    build(1,1,len);
    dij();
    if(T==2){
        for(int i=1;i<=n;i++){
            if(dist[i].fi==INF)cout<<0;
            else cout<<1;
        }
        cout<<endl;
    }else if(se==10){
        cout<<n<<m<<k<<endl;
        for(auto v:add)cout<<v.to<<" "<<v.c<<" "<<v.len<<endl;
        for(auto v:addk)cout<<v.fi<<" "<<endl;
    }
    
}
signed main(){ 
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << setiosflags(ios::fixed) << setprecision(15);
   
    T=1;
    cin>>T;
    for(se=1;se<=T;se++)solve();
    return 0;
}