大家倒垃圾的时候，都希望垃圾箱距离自己比较近，但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，同时还要保证每个居民点都在距离它一个不太远的范围内。

现给定一个居民区的地图，以及若干垃圾箱的候选地点，请你推荐最合适的地点。如果解不唯一，则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一，则输出编号最小的地点。

输入格式：

输入第一行给出4个正整数：N（<= 10³）是居民点的个数；M（<= 10）是垃圾箱候选地点的个数；K（<= 10⁴）是居民点和垃圾箱候选地点之间的道路的条数；D_S是居民点与垃圾箱之间不能超过的最大距离。所有的居民点从1到N编号，所有的垃圾箱候选地点从G1到GM编号。

随后K行，每行按下列格式描述一条道路：
P1 P2 Dist
其中P1和P2是道路两端点的编号，端点可以是居民点，也可以是垃圾箱候选点。Dist是道路的长度，是一个正整数。

输出格式：

首先在第一行输出最佳候选地点的编号。然后在第二行输出该地点到所有居民点的最小距离和平均距离。数字间以空格分隔，保留小数点后1位。如果解不存在，则输出“No Solution”。

输入样例1：

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

输出样例1：

G1

2.0 3.3

输入样例2：

2 1 2 10

1 G1 9

2 G1 20

输出样例2：

No Solution

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

#define INF 0x3f3f3f3f

#define MM(x) memset(x,0,sizeof(x))

using namespace std;

typedef long long LL;

const int N=10020;

typedef pair<int,double> psd;

vector<psd>E[1050];

double d[N];

int n,m,k;

double ds;

inline int bianhao(char s[])

{

	int len=strlen(s);

	int r=0;

	if(s[0]=='G')

	{

		for (int i=1; i<len; i++)

			r=r*10+(s[i]-'0');

		return 1000+r;

	}

	else

	{

		for (int i=0; i<len; i++)

			r=r*10+(s[i]-'0');

		return r;

	}

}

inline void spfa(const int &s,const int &t)

{

	d[s]=0;

	priority_queue<pair<double,int> >Q;

	Q.push(pair<double,int>(-d[s],s));

	while (!Q.empty())

	{

		int now=Q.top().second;

		Q.pop();

		for (int i=0; i<E[now].size(); i++)

		{

			int v=E[now][i].first;

			if(d[v]>d[now]+E[now][i].second)

			{

				d[v]=d[now]+E[now][i].second;

				Q.push(pair<double,int>(-d[v],v));

			}

		}

	}

}

struct info

{

	int s;

	double aver,sum,minm;

	info(const int &ss,const double &av,const double &su,const double &mm):s(ss),aver(av),sum(su),minm(mm){}

	info(){}

};

bool cmp(const info &a,const info &b)

{

	if(a.minm!=b.minm)

		return a.minm>b.minm;//就是这个地方写成了a.minm>b.sum，强行WA数次- -

	if(a.aver!=b.aver)

		return a.aver<b.aver;

	else

		return a.s<b.s;

}

int main(void)

{

	int i,j;

	while (~scanf("%d%d%d%lf",&n,&m,&k,&ds))

	{

		for (i=0; i<1050; i++)

			E[i].clear();

		char s[5],t[5];

		int S,T;

		double dx;

		for (i=0; i<k; i++)

		{

			scanf("%s%s%lf",s,t,&dx);

			S=bianhao(s);

			T=bianhao(t);

			E[S].push_back(psd(T,dx));

			E[T].push_back(psd(S,dx));

		}

		info ans[1000];int cnt=0;

		for (i=1; i<=m; i++)

		{

			memset(d,0x43,sizeof(d));

			for (j=1; j<=n; j++)

				spfa(i+1000,j);

			bool flag=1;

			double sss=0,tj,mm=1e6;

			for (j=1; j<=n; j++)

			{

				tj=d[j];

				if(tj>ds)

				{

					flag=0;

					break;

				}

				sss+=tj;

				if(tj<mm)

					mm=tj;

			}

			if(flag)

				ans[cnt++]=info(i,sss/n,sss,mm);

		}

		if(cnt==0)

			puts("No Solution");

		else

		{

			sort(ans,ans+cnt,cmp);

			printf("G%d\n%.1lf %.1lf\n",ans[0].s,ans[0].minm,ans[0].aver);

		}

	}

	return 0;

}