# include <iostream>
# include <algorithm>
# define MAX_N 10
# define INF 1e6

int n, m;

int d[MAX_N][MAX_N];

std::pair<int,int> solve(){
	for (int k = 0; k < n; ++k){
		for (int i = 0; i < n; ++i){
			for (int j = 0; j < n; ++j){
				d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			std::cout << d[i][j] << ' ';
		}
		std::cout << std::endl;
	}

	int min = (INF), minv;
	for (int i = 0; i < n; ++i){
		int plus = 0;
		for (int j = 0; j < n; ++j)
			plus += d[i][j];
		if (min > plus){
			min = plus;
			minv = i;
		}
	}
	return std::pair<int, int>(minv, min);
}

int main(){
	while (1){
		for (int i = 0; i < 10; ++i){
			for (int j = 0; j < 10; ++j)
				d[i][j] = INF;
		}
		int f, t, c;
		std::cin >> m;
		if (m == 0)
			break;
		
		for (int i = 0; i < m; ++i){
			std::cin >> f >> t >> c;
			n = std::max(n, f);
			n = std::max(n, t);
			d[f][t] = c;
			d[t][f] = c;
		}
		for (int i = 0; i < n; ++i)
			d[i][i] = 0;
		std::cout << solve().first << ' ' << solve().second << std::endl;
	}
	return 0;
}