Question 2: Need For Speed 4.1 Introduction
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 use special fiber connections. Lukarp has already planned the connections but feels some fiber connections are redundant. You have been hired by Lukarp to remove those fiber connections which don’t cause faster connections.
4.2 Problem Statement
4.2.1 The Problem
The offices and (bi-directional) connections (both normal and fiber) are given to you. HQ is numbered as 1. The ith normal connection connects any two offices ai and bi. Normal connections have latency li. The ith fiber connection connects the HQ with the office ci. Fiber connections also come with a latency pi. The total latency of a path is the sum of latencies on the connections. You are to output the maximum number of fiber connections that can be removed, such that the latency of the smallest latency path between the HQ and any other node remains the same as before.
• There are n offices with m normal connections and k high-speed fiber connections.
• The ith normal connection connects offices ai and bi (bi-directionally) with latency li.
• The ith fiber connection connects offices 1 and ci (bi-directionally) with latency pi.
4.2.2 Input Format
The first line of the input file will contain three space-separated integers n, m and k, the number of offices, the number of normal connections and the number of fiber connections.
There will be m lines after this, the ith line signifying the ith normal connection, each containing three space-separated integers ai, bi and li the two offices that are connected and the latency of the connection respectively.
There will be k lines after this, the ith line signifying the ith fiber connection, each containing three space-separated integers ci and pi, the office connected to the HQ and the latency of the fiber connection respectively.
6
4.2.3 Output Format
Output only one integer m - 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.
4.2.4 Constraints
• 2≤n≤105
• 1≤m≤2·105 • 1≤k≤105
• 1≤ai,bi,ci ≤n • 1≤li,pi ≤109
4.2.5 Example
Input:
452
122
149
133
244
345
34
45
Output:
1
Explanation:
In this example, there are five normal connections as shown in the figure below. The fiber connection going from 1 to 3 can be removed because the normal con- nection (3) is faster than the fiber connection (4). However, the fiber connection with 4 cannot be removed. Hence the maximum number of fiber connections that can be removed is 1.
7






/ Test cases


// 1 will be connected to all the nodes via normal connection.
/*



3 2 2
1 2 3
2 3 4
3 10
3 8

// ans=2


4 5 2 
1 2 2 
1 4 9
1 3 3
2 4 4
3 4 5
3 4
4 5

// ans =1 

3 3 3
1 2 5
1 3 100
2 3 1
2 4
3 2
3 1

//ans 2



4 4 2
1 2 5
2 3 4
3 4 1
1 4 10
2 1
4 8

// ans= 1

*/


/*
basic cases:

5 6 3
1 4 5
4 5 2
2 4 7
3 1 4
1 5 10
3 2 6
5 3
2 1
4 3

// ans = 0



4 4 1
2 3 2
2 4 8
4 3 1
1 4 5
3 7
// ans = 1

3 3 3
1 2 1
2 3 1
1 3 1
2 1
2 2
3 1
3

// ans 3 

4 5 2
1 2 2
1 4 9
1 3 3
2 4 4
3 4 5
3 4
4 5


// ans = 1





4 4 2
2 3 2
2 4 8
4 3 3
1 4 5
3 7
2 9

// ans = 1




4 4 2
1 2 5
2 3 4
3 4 1
1 4 10
2 1
4 8
// ans = 1


3 3 3
1 2 5
1 3 100
2 3 1
2 4
3 2
3 1
// ans = 2





\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

// Good testcases

5 6 3
1 4 5
4 5 2
2 4 7
3 1 4
1 5 10
3 2 6
2 1
4 3
5 5

// ans = 1


6 16 19
4 1 6
2 2 19
3 1 14
3 6 14
6 5 17
6 4 2
4 6 7
2 1 7
3 5 4
6 6 13
5 4 7
2 3 6
1 2 19
4 6 14
4 2 16
2 6 13
5  9
1  3
4  12
2  12
4  18
3  17
1  1
4  8
3  15
6  15
3  17
1  18
6  11
1  10
3  16
3  11
5  20
5  3
4  7


// ans = 18




3 9 8
1 1 14
1 3 1
2 2 12
3 1 15
3 1 19
3 3 15
1 3 7
3 1 8
1 2 6
2  18
3  1
2  13
3  2
3  5
1  20
2  8
3  5


// ans = 8

6 5 4
4 4 20
1 4 15 
5 3 14
5 5 12
2 6 19
6 3
4 10
1 18
4 4
// ans = 2



8 5 6
1 8 20
3 7 11
5 6 14
2 6 17
7 4 11
8 6
7 19
5 8
6 7
2 13
3 19
// ans = 0


10 10 10
9 8 2
8 8 9
2 8 17
1 1 1
6 6 10
10 8 11
3 9 18
7 1 5
3 2 17
5 5 10
3 16
1 20
8 13
3 7
5 12
1 10
10 14
10 3
4 1
3 3
// ans = 5


10 9 5
9 7 4
1 5 18
6 6 7
7 2 9
2 6 3
8 10 9
10 4 6
6 5 14
5 9 11
2 18
7 1
2 12
5 7
2 4
// ans = 2
*/


PROVIDE ME C++ IMPLEMENTATION , DONT TALK TOO MUCH  OR DONT EXPLAIN ANYTHING