#include "bits/stdc++.h"
#pragma GCC optimize "trapv"
using namespace std ;
const long double EPS = 1e-9 ;
const int MOD=1e9+7 ;
const int N = 4e5 + 5 ;
const int SZ = 2e5 ;
const long long inf = 2e15 ;
#define GOMO_GOMO_NOO ios_base::sync_with_stdio(0),cin.tie(0) , cout.tie(0) ;
#define ll long long
#define endl '\n'
#define all(v) v.begin() , v.end()
int ans = 0 ;
ll dis[N] ;
int main() {
GOMO_GOMO_NOO
int n , m , k ;
cin >> n >> m >> k ;
vector<vector<pair<int , pair<int , bool >>>> country(n + 1 ) ;
vector<bool> close(n + 1 , 0 ) ;
for (int u , v , w , i = 0; i < m ; ++i) {
cin >> u >> v >> w ;
country[u].push_back({v , {w , 0 } }) ;
country[v].push_back({u , {w , 0 } }) ;
}
vector<int> train ;
for (int i = 0; i < k; ++i) {
int x , y ;
cin >> x >> y ;
train.push_back(x) ;
country[1].push_back({x , {y , 1 }}) ;
country[x].push_back({1 , {y , 1 }}) ;
}
fill(dis , dis + N , inf) ;
set<pair<ll , pair<int , bool >>> st ;
st.insert({0 , {1 , 0} }) ;
dis[1] = 0 ;
while (!st.empty()){
ll cost = st.begin()->first ;
int node = st.begin()->second.first ;
st.erase(st.begin()) ;
if(cost > dis[node]){
continue;
}
for(auto i : country[node]){
ll total_cost = cost + i.second.first ;
int used = i.second.second ;
if(total_cost < dis[i.first]){
dis[i.first] = total_cost ;
st.insert({total_cost , {i.first , i.second.second }}) ;
close[i.first] = i.second.second ;
}else if(!used && dis[i.first] == total_cost){
close[i.first] = 0 ;
}
}
}
int cnt = count(all(close) , 1 ) ;
cout << k - cnt << endl ;
}
435. Non-overlapping Intervals | 406. Queue Reconstruction by Height |
380. Insert Delete GetRandom O(1) | 332. Reconstruct Itinerary |
368. Largest Divisible Subset | 377. Combination Sum IV |
322. Coin Change | 307. Range Sum Query - Mutable |
287. Find the Duplicate Number | 279. Perfect Squares |
275. H-Index II | 274. H-Index |
260. Single Number III | 240. Search a 2D Matrix II |
238. Product of Array Except Self | 229. Majority Element II |
222. Count Complete Tree Nodes | 215. Kth Largest Element in an Array |
198. House Robber | 153. Find Minimum in Rotated Sorted Array |
150. Evaluate Reverse Polish Notation | 144. Binary Tree Preorder Traversal |
137. Single Number II | 130. Surrounded Regions |
129. Sum Root to Leaf Numbers | 120. Triangle |
102. Binary Tree Level Order Traversal | 96. Unique Binary Search Trees |
75. Sort Colors | 74. Search a 2D Matrix |