(t=[1e9]*9<<m=0
d=(0..9).map{t=t.rotate -1}
$_.to_i.times{a,b,c=gets.split.map &:to_i;m=[a,b,m].max;d[a][b]=d[b][a]=c}
r=0..m
r.map{|k|r.map{|i|r.map{|j|d[i][j]>(t=d[i][k]+d[k][j])&&d[i][j]=t}}}
puts r.map{|i|s=0;r.map{|j|s+=d[i][j]};[i,s]}.min_by{|i,s|[s,i]}*" ")while gets>?1