http://poj.org/problem?id=1125
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 110
using namespace std;
const int INF=<<;
int dis[MAXN][MAXN];
int n,t,a,b;
void inti()
{
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
dis[i][j]=dis[j][i]=INF;
}
}
}
int main()
{
while(scanf("%d",&n)&&n)
{
inti();
for(int i=; i<=n; i++)
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&a,&b);
dis[i][a]=b;
}
}
for(int k=; k<=n; k++)
{
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
int cc,tt=-,mark=;
for(int i=; i<=n; i++)
{
int t=-,c;
bool flag=true;
for(int j=; j<=n; j++)
{
if(i!=j)
{
if(dis[i][j]==INF)
{
flag=false;
break;
}
else if(dis[i][j]>t)
{
c=i;
t=dis[i][j];
}
}
else continue;
}
if(flag)
{
if(mark)
{
cc=c;
tt=t;
mark=;
}
else if(t<tt)
{
cc=c;
tt=t;
}
}
}
if(tt==-) printf("disjoint\n");
else printf("%d %d\n",cc,tt);
}
return ;
}