def warshall_floyd(dist_matrix)
	dist = dist_matrix
	n = dist.size
	raise "dist_matrix is not square" if dist.any?{|row| row.size != n}

	(0..n-1).each{|k|
		next_dist = (1..n).map{ Array.new(n) }	
		(0..n-1).each{|i|
			(0..n-1).each{|j|
				x = dist[i][j]
				y = dist[i][k] + dist[k][j]
				next_dist[i][j] = (x < y ? x : y)
			}
		}
		dist = next_dist
	}
	dist
end


loop {
	m = gets.to_i
	break if m == 0
	dist_mat = (0..9).map{(0..9).map{Float::INFINITY}}
	(0..9).each{|i| dist_mat[i][i] = 0}
	m.times{
		i, j, d = gets.split.map &:to_i
		dist_mat[i][j] = d
		dist_mat[j][i] = d
	}
	while dist_mat.last.count(Float::INFINITY) == dist_mat.size - 1
		dist_mat.pop
		dist_mat.each(&:pop)
	end
	puts warshall_floyd(dist_mat).map.with_index{|r, i| [r.inject(:+), i]}.min.reverse * ' '
}