#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double

const int N = 5e5 + 10;

void solve() {
	
	int n , m , k; cin >> n >> m >> k;
	
	vector<priority_queue<pair<int , int> , vector<pair<int , int>> , greater<pair<int , int>>>> q(m + 1);
	vector<vector<array<int , 3>>> e(n + 1);
	for(int i = 1 ; i <= m ; i++){
		int u , v , c , l; cin >> u >> v >> c >> l;
		
		e[u].push_back({v , c , l});
		e[v].push_back({u , c , l});
	}
	
	for(auto [v , c , l] : e[1]){
		q[c].push({l , v});
	}

	vector<int> vis(n + 1 , 0);
	vis[1] = 1;
	for(int i = 1 ; i <= n ; i++){
		int a , b; cin >> a >> b;
		priority_queue<pair<int , int> , vector<pair<int , int>> , greater<pair<int , int>>> cur;
	
		while(q[a].size() && q[a].top().first <= b){
			auto [w , v] = q[a].top();
			cur.push({w , v});
			q[a].pop();
		}		
		
		while(cur.size()){
			auto [w , u] = cur.top(); cur.pop();
			
			if(vis[u]) continue;
			vis[u] = 1;
			
			for(auto [v , c , l] : e[u]){
				
				if(c == a && w + l <= b){
					cur.push({w + l , v});
				}
				else {
					q[c].push({l , v});
				}
			}
		}
	}
	
	for(int i = 1 ; i <= n ; i++) cout << vis[i];
	cout << '\n';
	
}

int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
   	
    int __ = 1;
    cin >> __;
    
	while(__--){
   		solve();
   	}
    return 0;
}