stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



#define int long long



#define rep(i,n) for(int i=0;i<(n);i++)

#define pb push_back

#define all(v) (v).begin(),(v).end()

#define fi first

#define se second

typedef vector<int>vint;

typedef pair<int,int>pint;

typedef vector<pint>vpint;



template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}

template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}



int N;

int A[333][333];



const int INF=1001001001001001001ll;

int d[333][333];



signed main(){

    cin>>N;

    rep(i,N)rep(j,N)cin>>A[i][j];



    fill_n(*d,333*333,INF);

    rep(i,N)d[i][i]=0;

    rep(i,N)rep(j,N)chmin(d[i][j],A[i][j]);



    rep(k,N)rep(i,N)rep(j,N)chmin(d[i][j],d[i][k]+d[k][j]);



    rep(i,N)rep(j,N)if(d[i][j]!=A[i][j]){

    cout<<-1<<endl;

    return 0;}



    int ans=0;

    rep(i,N)for(int j=i+1;j<N;j++){

        bool f=false;

        rep(k,N){

            if(i==k||j==k)continue;

            if(d[i][k]+d[k][j]==d[i][j])f=true;

        }

        if(!f)ans+=d[i][j];

    }



    cout<<ans<<endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.891099211166235x):
#include<bits/stdc++.h>

using namespace std;



#define int long long



#define rep(i,n) for(int i=0;i<(n);i++)

#define pb push_back

#define all(v) (v).begin(),(v).end()

#define fi first

#define se second

typedef vector<int>vint;

typedef pair<int,int>pint;

typedef vector<pint>vpint;



template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}

template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}



int N;

int A[333][333];



signed main(){

    cin>>N;

    rep(i,N)rep(j,N)cin>>A[i][j];



    int ans=0;

    rep(i,N)for(int j=i+1;j<N;j++){

        bool flag=false;

        rep(k,N){

            if(A[i][k]+A[k][j]<A[i][j]){

                cout<<-1<<endl;

                return 0;

            }

            if(A[i][k]+A[k][j]>A[i][j])continue;

            if(i!=k&&j!=k)flag=true;

        }

        if(!flag)ans+=A[i][j];

    }

    cout<<ans<<endl;

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <list>

#include <vector>

#include <unistd.h>

#include <algorithm>

#define ll long long

using namespace std;

ll N;

ll m[301][301]; 

int main(){

	cin >> N;

	memset(m, -1, sizeof(m));

	for ( ll i = 0 ; i < N ; i ++ ){

		for ( ll j = 0 ; j < N ; j ++ ){

			cin >> m[i][j];

		}

	}

	ll tot = 0;

	for ( ll i = 0 ; i < N ; i ++ ){

		for ( ll j = 0 ; j < N ; j ++ ){

			if ( i == j ) continue;

			bool flag = true;

			for ( ll k = 0 ; k < N ; k ++ ){

				if ( k == i || k == j ) continue;

				if ( m[i][k] + m[k][j] < m[i][j] )  {

					cout << -1 << endl;

					return 0;

				}

				if ( m[i][k] + m[k][j] == m[i][j] ) flag = false;

			}

			if ( flag ){

					tot += m[i][j];

			}                

		}

	}

	cout << tot / 2 << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.7259726556611936x):
#include<bits/stdc++.h>

using namespace std;

#define inf 1000000008

int w[305][305],dist[305][305];

int main()

{

    int n,i,j,k;

    long long ans=0,sum=0;

    cin>>n;

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

    {

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

        {

            cin>>dist[i][j];

            sum+=dist[i][j];

            //dist[i][j]=w[i][j];

        }

    }

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

    {

        dist[i][i]=inf;

    }

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

    {

        // Pick all vertices as source one by one

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

        {

            // Pick all vertices as destination for the

            // above picked source

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

            {

                if (dist[i][k] + dist[k][j] == dist[i][j])

                {

                    if(!w[i][j])

                    {

                        //cout<<dist[i][j]<<endl;

                        ans+=dist[i][j];

                        w[i][j]=1;

                    }

                }

                if (dist[i][k] + dist[k][j] < dist[i][j])

                {

                    dist[i][j] = dist[i][k] + dist[k][j];

                    printf("-1\n");

                    return 0;

                }

            }

        }

    }

    cout<<(sum/2)-ans<<endl;

}
// Slower C++ solution:
#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <list>

#include <vector>

#include <unistd.h>

#include <algorithm>

#define ll long long

using namespace std;

ll N;

ll m[301][301]; 

int main(){

	cin >> N;

	memset(m, -1, sizeof(m));

	for ( ll i = 0 ; i < N ; i ++ ){

		for ( ll j = 0 ; j < N ; j ++ ){

			cin >> m[i][j];

		}

	}

	ll tot = 0;

	for ( ll i = 0 ; i < N ; i ++ ){

		for ( ll j = 0 ; j < N ; j ++ ){

			if ( i == j ) continue;

			bool flag = true;

			for ( ll k = 0 ; k < N ; k ++ ){

				if ( k == i || k == j ) continue;

				if ( m[i][k] + m[k][j] < m[i][j] )  {

					cout << -1 << endl;

					return 0;

				}

				if ( m[i][k] + m[k][j] == m[i][j] ) flag = false;

			}

			if ( flag ){

					tot += m[i][j];

			}                

		}

	}

	cout << tot / 2 << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.6463109935332159x):
#include<bits/stdc++.h>



using namespace std;

#define MXX 305

typedef pair<int,int> ii;

vector<ii> adj[1000];

vector<int> t_adj[1000];

bool visited[1000];

long long adj_mat[MXX][MXX];





void add_edge(int u,int v,int c)

{

    adj[u].push_back(ii(c,v));

    adj[v].push_back(ii(c,u));



}



bool flag[MXX][MXX];



void floydwarshall(int n)

{



    for(int k=0; k<n; k++)

    {

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

        {

            for(int j=0; j<n; j++)

            {

                if(adj_mat[i][k]+adj_mat[k][j]<adj_mat[i][j])

                {

                    adj_mat[i][j]=adj_mat[i][k]+adj_mat[k][j];

                }

                else if(adj_mat[i][k]+adj_mat[k][j]==adj_mat[i][j] && i!=k && j!=k)

                {

                    flag[i][j]=true;

                }

            }

        }

    }

}



int main()

{

    int n;

    long long ans=0;



        cin>>n;

        int mat[n][n];

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

        {

            for(int j=0; j<n; j++)

            {

                cin>>mat[i][j];

                adj_mat[i][j]=mat[i][j];

            }

        }



        floydwarshall(n);

        bool f=false;

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

        {

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

            {



                if(adj_mat[i][j]!=mat[i][j])

                {

                    f=true;

                    break;

                }

                else if(!flag[i][j])

                ans+=adj_mat[i][j];

            }

        }

        if(f)

        cout<<-1<<endl;

        else cout<<ans<<endl;

}
// Slower C++ solution:
#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <list>

#include <vector>

#include <unistd.h>

#include <algorithm>

#define ll long long

using namespace std;

ll N;

ll m[301][301]; 

int main(){

	cin >> N;

	memset(m, -1, sizeof(m));

	for ( ll i = 0 ; i < N ; i ++ ){

		for ( ll j = 0 ; j < N ; j ++ ){

			cin >> m[i][j];

		}

	}

	ll tot = 0;

	for ( ll i = 0 ; i < N ; i ++ ){

		for ( ll j = 0 ; j < N ; j ++ ){

			if ( i == j ) continue;

			bool flag = true;

			for ( ll k = 0 ; k < N ; k ++ ){

				if ( k == i || k == j ) continue;

				if ( m[i][k] + m[k][j] < m[i][j] )  {

					cout << -1 << endl;

					return 0;

				}

				if ( m[i][k] + m[k][j] == m[i][j] ) flag = false;

			}

			if ( flag ){

					tot += m[i][j];

			}                

		}

	}

	cout << tot / 2 << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.7458711796181927x):
#include <bits/stdc++.h>



using namespace std;



int main() { 

	

	//freopen ("in.txt", "r", stdin);

	

	int t;

	scanf ("%d", &t);

	

	long a[t][t];

	

	for (int i=0; i<t; i++) for (int j=0; j<t; j++) scanf ("%ld", &a[i][j]);

	

	long sum = 0;

	bool mark[t][t];

	memset(mark, false, sizeof mark);

	bool impossible = false;

	for (int i=0; i<t; i++) { 

		for (int j=0; j<t; j++) { 

			for (int k=j+1; k<t; k++) { 

				if(a[j][k]==a[j][i]+a[i][k] && i!=j && i!=k) mark[j][k] = true;

				if(a[j][k]>a[j][i]+a[i][k]) { 

					impossible = true;

					break;

				}

			}

		}		

	}

	if(impossible) { printf ("-1\n");  return 0;}

	for (int i=0; i<t; i++) for (int j=i+1; j<t;j++) if(!mark[i][j]) sum+=a[i][j];

	

	

	

		printf ("%ld\n", sum);

	

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



int N;

int p[8],q[8];

vector<int> dic(40325);

int idx=0;



int kaijo(int n){

  int ans=1;

  for(int i=1;i<=n;i++) ans*=i;

  return ans;

}



bool is_d_in_x(int d, int x){

  while(x>0){

    int res= x%10;

    if(res==d) return false;

    x/=10;

  }



  return true;

}



int digits(int x){

  int d=0;

  while(x>0){

    x/=10;

    d++;

  }

  return d;

}



void dfs(int d){

  if(digits(d)==N) {

    dic[idx]=d;

    idx++;



    return;

  }

  for(int i=1;i<=N;i++){



    if(is_d_in_x(i,d)){

      dfs(d*10+i);

    }

  }

}

int main() {



  cin>>N;



  for(int i=0;i<N;i++) cin>>p[i];

  for(int i=0;i<N;i++) cin>>q[i];

  int P=0,Q=0;

  for(int i=0;i<N;i++){

    P+=p[N-1-i]*long(pow(10,i));

  }

  for(int i=0;i<N;i++){

    Q+=q[N-1-i]*long(pow(10,i));

  }



  int l,r;



  dfs(0);

  sort(dic.begin(),dic.begin()+kaijo(N));



  int a,b;

  for(int i=0;i<kaijo(N);i++){

    if(dic[i]==P) a=i;

    if(dic[i]==Q) b=i;

  }

  cout<<abs(a-b)<<endl;









}


// Faster C++ solution for the same problem (measured speedup: 1.1574458363477136x):
#include <bits/stdc++.h>

using namespace std;



int N;



bool same(vector<int> a,vector<int> b){

  for(int i=0;i<N;i++){

    if(a[i]!=b[i]) return false;

  }

  return true;

}

int kaijo(int N){

  int ans=1;

  for(int i=1;i<=N;i++){

    ans*=i;

  }

  return ans;

}

int main() {



  cin>>N;

  vector<int> d(N);

  for(int i=0;i<N;i++) d[i]=i+1;

  vector<int> a(N);

  vector<int> b(N);

  for(int i=0;i<N;i++) cin>>a[i];

  for(int i=0;i<N;i++) cin>>b[i];





  int da=0,db=0;

  for(int i=0;i<kaijo(N);i++){

    if(same(a,d)) da=i;

    if(same(b,d)) db=i;

    next_permutation(d.begin(),d.end());

  }

  cout<<abs(da-db)<<endl;





  }
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



int N;

int p[8],q[8];

vector<int> dic(40325);

int idx=0;



int kaijo(int n){

  int ans=1;

  for(int i=1;i<=n;i++) ans*=i;

  return ans;

}



bool is_d_in_x(int d, int x){

  while(x>0){

    int res= x%10;

    if(res==d) return false;

    x/=10;

  }



  return true;

}



int digits(int x){

  int d=0;

  while(x>0){

    x/=10;

    d++;

  }

  return d;

}



void dfs(int d){

  if(digits(d)==N) {

    dic[idx]=d;

    idx++;



    return;

  }

  for(int i=1;i<=N;i++){



    if(is_d_in_x(i,d)){

      dfs(d*10+i);

    }

  }

}

int main() {



  cin>>N;



  for(int i=0;i<N;i++) cin>>p[i];

  for(int i=0;i<N;i++) cin>>q[i];

  int P=0,Q=0;

  for(int i=0;i<N;i++){

    P+=p[N-1-i]*long(pow(10,i));

  }

  for(int i=0;i<N;i++){

    Q+=q[N-1-i]*long(pow(10,i));

  }



  int l,r;



  dfs(0);

  sort(dic.begin(),dic.begin()+kaijo(N));



  int a,b;

  for(int i=0;i<kaijo(N);i++){

    if(dic[i]==P) a=i;

    if(dic[i]==Q) b=i;

  }

  cout<<abs(a-b)<<endl;









}


// Faster C++ solution for the same problem (measured speedup: 1.1578160902091696x):
#include <bits/stdc++.h>

using namespace std;



int N;



int kaijo(int n){

  int r=1;

  for(int i=1;i<=n;i++){

    r*=i;

  }

  return r;

}



bool same(vector<long> x,vector<long> y){

  bool flg=true;

  for(int i=0;i<N;i++){

    if(x[i]!=y[i]) flg=false;

  }

  return flg;

}

int main() {





cin>>N;

vector<long> p(N);

vector<long> q(N);



for(int i=0;i<N;i++) cin>>p[i];

for(int i=0;i<N;i++) cin>>q[i];



vector<long> a(N);

for(int i=0;i<N;i++) a[i]=i+1;

long P,Q;

for(int i=0;i<kaijo(N);i++){

  if(same(a,p)) P=i;

  if(same(a,q)) Q=i;

  next_permutation(a.begin(),a.end());

}

cout<<abs(P-Q)<<endl;

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

#include<string.h>

#include<math.h>

#include<stdio.h>

#include<queue>

#define INF 0x3f3f3f3f

typedef long long ll;

using namespace std;



#define  N 15

int n;

int dis[N],maps[N][N];

int main()

{

    int i,a,b,c,j,k;

    while(scanf("%d",&n),n)

    {

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

        {

            for(j=0;j<N;j++)

            {

                maps[i][j]=(i==j)?0:INF;

            }

        }



        int m=-1;

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

        {

            scanf("%d%d%d",&a,&b,&c);

            m=max(a,m);

            m=max(b,m);

            maps[a][b]=maps[b][a]=c;

        }



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

        {

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

            {

                for(j=0;j<=m;j++)

                {

                    if(maps[i][j]>maps[i][k]+maps[k][j])

                        maps[i][j]=maps[i][k]+maps[k][j];

                }

            }

        }



        int  Min=INF;

        int index=-1;

        memset(dis,0,sizeof(dis));

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

        {

            for(j=0;j<=m;j++)

            {

                dis[i]=dis[i]+maps[i][j];

            }

            if(Min>dis[i])

            {

                index=i;

                Min=dis[i];

            }

        }

        printf("%d %d\n",index,Min);

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.066795937861301x):
#include<cstdio>

#include<algorithm>

#include<string.h>

using namespace std;

int main()

{

	int t,map[12][12],sum,ans,s,i,j,k,max0,a,b,c;

	while(scanf("%d",&t) && t)

	{

		memset(map,1,sizeof(map));

		max0=0;

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

		{

			scanf("%d %d %d",&a,&b,&c);

			map[a][b]=map[b][a]=c;

			max0=max(max0,max(a,b));

		}

	/*	printf("%d\n\n",max0);

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

		 {

		 	for(j=0;j<=max0;j++)

		 	{

		 		printf("%d  ",map[i][j]);

		 		if(j == max0)

		 			printf("\n");

			 }

		 }*/

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

		{

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

			{

				for(j=0;j<=max0;j++)

				{

					map[i][j]=min(map[i][j],map[i][k]+map[k][j]);

				}

			}

		}

		sum=10000000,ans=0;

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

		{

			s=0;

			for(j=0;j<=max0;j++)

			{

				if(i != j)

				{

					s+=map[i][j];

				}

			}

			if(s < sum)

			{

				sum=s;

				ans=i;

			}

		}

		printf("%d %d\n",ans,sum);

	}

}
// Slower C++ solution:
#include<stdio.h>

#include<string.h>

#include<algorithm>

#define INF 0xfffffff

using namespace std;

int map[1100][1100];

int main()

{

	int n,m,k,i,j,a,b,c,sum1;

	while(scanf("%d",&n),n)

	{

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

		for(j=0;j<1100;j++)

		{

			map[i][j]=INF;

			map[i][i]=0;

		}

		int Max=0;

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

		{

			scanf("%d%d%d",&a,&b,&c);

			Max=max(Max,a);

			Max=max(Max,b);

			map[a][b]=c;

			map[b][a]=c;

		}

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

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

		for(j=0;j<=Max;j++)

		{

			if(map[i][j]>map[i][k]+map[k][j])

			map[i][j]=map[i][k]+map[k][j];

		}

		int sum=INF;

		int ans=0;

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

		{

			sum1=0;

			for(j=0;j<=Max;j++)

		    {

			   sum1+=map[i][j];

		    }

		    if(sum1<sum)

			{

				sum=sum1;

				ans=i;

			}

		}

		printf("%d %d\n",ans,sum);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 46.71460485584292x):
#include<cstdio>

#include<algorithm>

#include<string.h>

using namespace std;

int main()

{

	int t,map[12][12],sum,ans,s,i,j,k,max0,a,b,c;

	while(scanf("%d",&t) && t)

	{

		memset(map,1,sizeof(map));

		max0=0;

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

		{

			scanf("%d %d %d",&a,&b,&c);

			map[a][b]=map[b][a]=c;

			max0=max(max0,max(a,b));

		}

	/*	printf("%d\n\n",max0);

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

		 {

		 	for(j=0;j<=max0;j++)

		 	{

		 		printf("%d  ",map[i][j]);

		 		if(j == max0)

		 			printf("\n");

			 }

		 }*/

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

		{

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

			{

				for(j=0;j<=max0;j++)

				{

					map[i][j]=min(map[i][j],map[i][k]+map[k][j]);

				}

			}

		}

		sum=10000000,ans=0;

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

		{

			s=0;

			for(j=0;j<=max0;j++)

			{

				if(i != j)

				{

					s+=map[i][j];

				}

			}

			if(s < sum)

			{

				sum=s;

				ans=i;

			}

		}

		printf("%d %d\n",ans,sum);

	}

}
// Slower C++ solution:
#include<stdio.h>  

#include<string.h>  

#include<algorithm>  

#define INF 0xfffffff  

using namespace std;  

int map[1100][1100];  

int main()  

{  

    int n,m,k,i,j,a,b,c,sum1;  

    while(scanf("%d",&n),n)  

    {  

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

        for(j=0;j<1100;j++)  

        {  

            map[i][j]=INF;  

            map[i][i]=0;  

        }  

        int Max=0;  

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

        {  

            scanf("%d%d%d",&a,&b,&c);  

            Max=max(Max,a);  

            Max=max(Max,b);  

            map[a][b]=c;  

            map[b][a]=c;  

        }  

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

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

        for(j=0;j<=Max;j++)  

        {  

            if(map[i][j]>map[i][k]+map[k][j])  

            map[i][j]=map[i][k]+map[k][j];  

        }  

        int sum=INF;  

        int ans=0;  

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

        {  

            sum1=0;  

            for(j=0;j<=Max;j++)  

            {  

               sum1+=map[i][j];  

            }  

            if(sum1<sum)  

            {  

                sum=sum1;  

                ans=i;  

            }  

        }  

        printf("%d %d\n",ans,sum);  

    }  

    return 0;  

}  

// Faster C++ solution for the same problem (measured speedup: 46.71460485584292x):
#include<cstdio>

#include<algorithm>

#include<string.h>

using namespace std;

int main()

{

	int t,map[12][12],sum,ans,s,i,j,k,max0,a,b,c;

	while(scanf("%d",&t) && t)

	{

		memset(map,1,sizeof(map));

		max0=0;

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

		{

			scanf("%d %d %d",&a,&b,&c);

			map[a][b]=map[b][a]=c;

			max0=max(max0,max(a,b));

		}

	/*	printf("%d\n\n",max0);

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

		 {

		 	for(j=0;j<=max0;j++)

		 	{

		 		printf("%d  ",map[i][j]);

		 		if(j == max0)

		 			printf("\n");

			 }

		 }*/

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

		{

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

			{

				for(j=0;j<=max0;j++)

				{

					map[i][j]=min(map[i][j],map[i][k]+map[k][j]);

				}

			}

		}

		sum=10000000,ans=0;

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

		{

			s=0;

			for(j=0;j<=max0;j++)

			{

				if(i != j)

				{

					s+=map[i][j];

				}

			}

			if(s < sum)

			{

				sum=s;

				ans=i;

			}

		}

		printf("%d %d\n",ans,sum);

	}

}
// Slower C++ solution:
#include<stdio.h>

#include<string.h>

#include<algorithm>

#define INF 0xfffffff

using namespace std;

int map[1100][1100];

int main()

{

	int n,m,k,i,j,a,b,c,sum1;

	while(scanf("%d",&n),n)

	{

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

		for(j=0;j<1100;j++)

		{

			map[i][j]=INF;

			map[i][i]=0;

		}

		int Max=0;

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

		{

			scanf("%d%d%d",&a,&b,&c);

			Max=max(Max,a);

			Max=max(Max,b);

			map[a][b]=c;

			map[b][a]=c;

		}

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

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

		for(j=0;j<=Max;j++)

		{

			if(map[i][j]>map[i][k]+map[k][j])

			map[i][j]=map[i][k]+map[k][j];

		}

		int sum=INF;

		int ans=0;

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

		{

			sum1=0;

			for(j=0;j<=Max;j++)

		    {

			   sum1+=map[i][j];

		    }

		    if(sum1<sum)

			{

				sum=sum1;

				ans=i;

			}

		}

		printf("%d %d\n",ans,sum);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 9.198181020158323x):
#include <iostream>

#include <cstdio>

#include <set>

#include <queue>

#include <cstring>

#include <algorithm>

using namespace std;

#define INF 0x3f3f3f3f

int dis[50][50];

int main()

{

    int m,a,ans,b,oop,n,op;

    while(~scanf("%d",&n)&&n)

    {

        m = 0;

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

        {

            for(int j = 0 ; j <20 ;j++)

                dis[i][j] = INF;

        }

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

        {

            scanf("%d%d",&a,&b);

            scanf("%d",&dis[a][b]);

            dis[b][a] = dis[a][b];

            if(m < a||m < b)

            {

                if(a<b)  m = b;

                else    m = a;

            }

        }

        for(int i = 0; i <= m; i++)  dis[i][i] = 0;

        for(int k = 0; k <= m; k++)

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

                for(int j = 0; j <= m; j++)

                {

                    if(dis[i][j] > dis[i][k] + dis[k][j])

                   {

                       dis[i][j] = dis[i][k] + dis[k][j];

                       dis[j][i] = dis[i][k] + dis[k][j];

                   }

                }

        oop = INF;

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

        {

            ans = 0;

            for(int u = 0 ; u <= m; u++)

            {

                if(dis[i][u] != INF)

                    ans += dis[i][u];

            }

            if(ans<oop)

            {

                op = i;

                oop = ans;

            }

        }

        printf("%d %d\n",op,oop);

    }

    return 0;

}
// Slower C++ solution:
#include<stdio.h>  

#include<string.h>  

#include<algorithm>  

#define INF 0xfffffff  

using namespace std;  

int map[1100][1100];  

int main()  

{  

    int n,m,k,i,j,a,b,c,sum1;  

    while(scanf("%d",&n),n)  

    {  

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

        for(j=0;j<1100;j++)  

        {  

            map[i][j]=INF;  

            map[i][i]=0;  

        }  

        int Max=0;  

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

        {  

            scanf("%d%d%d",&a,&b,&c);  

            Max=max(Max,a);  

            Max=max(Max,b);  

            map[a][b]=c;  

            map[b][a]=c;  

        }  

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

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

        for(j=0;j<=Max;j++)  

        {  

            if(map[i][j]>map[i][k]+map[k][j])  

            map[i][j]=map[i][k]+map[k][j];  

        }  

        int sum=INF;  

        int ans=0;  

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

        {  

            sum1=0;  

            for(j=0;j<=Max;j++)  

            {  

               sum1+=map[i][j];  

            }  

            if(sum1<sum)  

            {  

                sum=sum1;  

                ans=i;  

            }  

        }  

        printf("%d %d\n",ans,sum);  

    }  

    return 0;  

}  

// Faster C++ solution for the same problem (measured speedup: 9.198181020158323x):
#include <iostream>

#include <cstdio>

#include <set>

#include <queue>

#include <cstring>

#include <algorithm>

using namespace std;

#define INF 0x3f3f3f3f

int dis[50][50];

int main()

{

    int m,a,ans,b,oop,n,op;

    while(~scanf("%d",&n)&&n)

    {

        m = 0;

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

        {

            for(int j = 0 ; j <20 ;j++)

                dis[i][j] = INF;

        }

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

        {

            scanf("%d%d",&a,&b);

            scanf("%d",&dis[a][b]);

            dis[b][a] = dis[a][b];

            if(m < a||m < b)

            {

                if(a<b)  m = b;

                else    m = a;

            }

        }

        for(int i = 0; i <= m; i++)  dis[i][i] = 0;

        for(int k = 0; k <= m; k++)

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

                for(int j = 0; j <= m; j++)

                {

                    if(dis[i][j] > dis[i][k] + dis[k][j])

                   {

                       dis[i][j] = dis[i][k] + dis[k][j];

                       dis[j][i] = dis[i][k] + dis[k][j];

                   }

                }

        oop = INF;

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

        {

            ans = 0;

            for(int u = 0 ; u <= m; u++)

            {

                if(dis[i][u] != INF)

                    ans += dis[i][u];

            }

            if(ans<oop)

            {

                op = i;

                oop = ans;

            }

        }

        printf("%d %d\n",op,oop);

    }

    return 0;

}