Find Friends in a City Graph

You are given an undirected weighted graph representing a network of cities and roads. Each road connects two cities and has an associated length. Two distinct cities are called friends if the length of the shortest path between them is at most \(K\). Your task is to find and print all pairs of cities \((u, v)\) (with \(u < v\)) that are friends.

Note: The graph may be disconnected, and if no pair of friends exists for a test case, nothing should be printed for that test case.

Input/Output Format: See below.

inputFormat

The input is read from stdin and follows this format:

1. The first line contains an integer \(T\) denoting the number of test cases.
2. For each test case:
   • The first line contains three space-separated integers: \(N\), \(M\) and \(K\), where \(N\) is the number of cities, \(M\) is the number of roads, and \(K\) is the maximum allowed distance.
   • This is followed by \(M\) lines, each containing three integers \(u\), \(v\) and \(w\), representing an undirected road between city \(u\) and city \(v\) with length \(w\).

It is guaranteed that \(1 \leq u, v \leq N\) and \(u \neq v\). Roads may appear in any order.

outputFormat

For each test case, print all friend pairs \((u, v)\) (with \(u < v\)) in sorted order (first by \(u\), then by \(v\)). Each pair should be printed on a separate line in the format:

u v

If no friend pairs exist for a test case, print nothing. For multiple test cases, separate the outputs by a blank line. The output should be written to stdout.

## sample

1
4 5 10
1 2 5
2 3 5
3 4 5
1 3 10
2 4 15

1 2
1 3
2 3
2 4
3 4

</p>