#include <bits/stdc++.h>
using namespace std;


void add_edge(vector<vector<int>> &adj, int u, int v, int l)
{
    if (u >= 1 && u <= adj.size() - 1 && v >= 1 && v <= adj.size() - 1)
    {
        adj[u][v] = l;
        adj[v][u] = l;
    }
}

void func(vector<int> &dist1, vector<int> &adj2, int n)
{
    int cnt = 0;
    for (int i = 1; i <= n; i++)
       { if (dist1[i] <= adj2[i])
            cnt++;}
    cout << cnt;
}

void dijkstra(vector<vector<int>> &adj, int src, int n, vector<int> &dist)
{
    vector<int>dijkstra (adj,src);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq; 
      vector<int>dist(n);

    for(int i=0;i<n;i++)
    {
        dist[i]=100000;
    }
    dist[src]=0;
    pq.push({0,src});
    while(!pq.empty())
    {
        int dist=pq.front.first;
        int node=pq.front..second;
        pq.pop();
        for(auto it:adj[node])
        {
            int d=it.first;
            int n=it.second;
            if(dist[node]+d<dist[n])
            {
                dist[n]=dist[node]+d;
            }
            pq.push({dist[node],n});
        }
    }

}

int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> adj1(n + 1, vector<int>(n + 1, 100000));
    // vector<vector<int>> adj2(n + 1, vector<int>(n + 1, 100000));
    vector<int> adj2(n+1, 100000);
    vector<int> dist1(n + 1, 100000);

    for (int i = 0; i < m; i++)
    {
        int u, v, l;
        cin >> u >> v >> l;
        add_edge(adj1, u, v, l);
    }

    for (int i = 0; i < k; i++)
    {
        int v, l;
        cin >> v >> l;
        adj2[v] = l;
        //  add_edge(adj2, 0, v, l);
    }

    dijkstra(adj1, 1, n, dist1);
    // dijkstra(adj2, 1, n, dist2);
    func(dist1, adj2, n);

    return 0;
}


Lukarp has started his own tech company. He received a lot of funding from Igen with which he opened many offices around the world. Each office needs to communicate with one other, for which they're using high speed connections between the offices. Office number 1 is Lukarp's HQ. Some offices are important and hence need faster connections to the HQ for which Lukarp has used special fiber connections. Lukarp has already planned the connections but feels some fiber connections are redundant. You have been hired by Lukarp to remove the fiber connections which don't cause faster connections.

Statement
The offices and (bi-directional) connections (both normal and fiber) are given to you. 
. The 
 normal connection connects any two offices 
 and 
. Normal connections have latency 
. The 
 fiber connection connects the HQ with the office 
. Fiber connections also come with a latency 
. The total latency of a path is the sum of latencies on the connections. You are to output the 
 that can be removed, such that the 
 between the HQ and any other node remains the same as before.

There are 
 offices with 
 normal connections and 
 high-speed fiber connections.
The 
 normal connection connects offices 
 and 
 (bi-directionally) with latency 
.
The 
 fiber connection connects offices 
 and 
 (bi-directionally) with latency 
.
Input Format
The first line of the input file will contain three space-separated integers 
, 
 and 
, the number of offices, the number of normal connections and the number of fiber connections.

There will be 
 lines after this, the 
 line signifying the 
 normal connection, each containing three space-separated integers 
, 
 and 
 the two offices that are connected and the latency of the connection respectively.

There will be 
 lines after this, the 
 line signifying the 
 fiber connection, each containing three space-separated integers 
 and 
, the office connected to the HQ and the latency of the fiber connection respectively.

Output Format
Output only one integer 
 - the maximum number of fiber connections that can be removed without changing the latency of smallest latency path from office 1 to any other office.

Constraints




Note: There may be multiple connections of either type between two offices, and an office might be connected to itself as well.

Samples
Input

Copy
4 5 2
1 2 2
1 4 9
1 3 3
2 4 4
3 4 5
3 4
4 5
Output

Copy
1