PROGRAMMING:Distribution of dustbins
When we take out the garbage, we all hope that the garbage can is close to us, but no one wants to live in the garbage can. Therefore, the location of the dustbin must be the shortest and longest distance to all the residential areas, and at the same time, each residential area must be within a not too far distance from it.
Now, given a map of a residential area and a number of candidate locations for dustbins, please recommend the most suitable location. If the solution is not unique, the solution with the shortest average distance to all settlements will be output. If the solution is not unique, the location with the smallest number will be output.
###Input format:
Enter the first line to give four positive integers: $$n $$($$Le 10 ^ 3 $$) is the number of settlements$$ M $$($$Le 10 $$) is the number of candidate locations of garbage cans$$ K $$($$Le 10 ^ 4 $$) is the number of roads between the residential area and the candidate location of the dustbin$$ D_ S $$is the maximum distance between the residential area and the garbage can. All settlements are numbered from 1 to $$n $, and all trash can candidates are numbered from $$G1 $$to $$GM $.
This is followed by $$k $$lines, each describing a road in the following format:
```
P1 P2 Dist
```
Among them, 'P1' and 'P2' are the numbers of the two ends of the road, and the end point can be a residential area or a garbage can candidate point` Dist 'is the length of the road, a positive integer.
###Output format:
First, output the number of the best candidate location in the first line. Then output the minimum distance and average distance from the location to all settlements in the second line. The numbers are separated by spaces and 1 decimal place is reserved. If the solution does not exist, output 'no solution'.
###Input sample 1:
```in
4 3 11 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2
```
###Output sample 1:
```out
G1
2.0 3.3
```
###Input example 2:
```
2 1 2 10
1 G1 9
2 G1 20
```
###Output example 2:
```
No Solution
```
answer：If there is no answer, please comment
Now, given a map of a residential area and a number of candidate locations for dustbins, please recommend the most suitable location. If the solution is not unique, the solution with the shortest average distance to all settlements will be output. If the solution is not unique, the location with the smallest number will be output.
###Input format:
Enter the first line to give four positive integers: $$n $$($$Le 10 ^ 3 $$) is the number of settlements$$ M $$($$Le 10 $$) is the number of candidate locations of garbage cans$$ K $$($$Le 10 ^ 4 $$) is the number of roads between the residential area and the candidate location of the dustbin$$ D_ S $$is the maximum distance between the residential area and the garbage can. All settlements are numbered from 1 to $$n $, and all trash can candidates are numbered from $$G1 $$to $$GM $.
This is followed by $$k $$lines, each describing a road in the following format:
```
P1 P2 Dist
```
Among them, 'P1' and 'P2' are the numbers of the two ends of the road, and the end point can be a residential area or a garbage can candidate point` Dist 'is the length of the road, a positive integer.
###Output format:
First, output the number of the best candidate location in the first line. Then output the minimum distance and average distance from the location to all settlements in the second line. The numbers are separated by spaces and 1 decimal place is reserved. If the solution does not exist, output 'no solution'.
###Input sample 1:
```in
4 3 11 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2
```
###Output sample 1:
```out
G1
2.0 3.3
```
###Input example 2:
```
2 1 2 10
1 G1 9
2 G1 20
```
###Output example 2:
```
No Solution
```
answer：If there is no answer, please comment