#/***********************************************************
#    dijkstra.rb -- 最短路問題
#    使用例: dijkstra <dijkstra.dat
#***********************************************************/

INT_MAX = 2147483647
NMAX = 100
row = []; (NMAX + 1).times{ row.push(0) }
$weight = []; (NMAX + 1).times{ $weight.push(row.dup) }

def readweight            # データ入力 
    if ((n = gets.to_i) == nil || n > NMAX) 
        n = 0;  return
    end
    for i in 1..n
        for j in 1..n; $weight[i][j] = INT_MAX; end
    end
    while ((i, j, x = gets.scan(/\S+/).collect{|x| x.to_f}).size == 3)
        $weight[i][j] = $weight[j][i] = x
    end
    printf("データ weight(i,j)\n")
    for i in 1..n
        for j in 1..n
            if ($weight[i][j] < INT_MAX)
                printf("%3d", $weight[i][j])
            else
                printf(" ∞")
            end
        end
        printf("\n")
    end
    return n
end

START = 1

visited = []
distance = []; prev = []

n = readweight()  # 点の数\tt nend, 距離\tt $weight[1..n][1..n]endを読む 
for i in 1..n
    visited[i] = false;  distance[i] = INT_MAX
end
distance[START] = 0;  nxt = START
begin 
    i = nxt;  visited[i] = true;  min = INT_MAX
    for j in 1..n
        if (visited[j]); next; end
        if ($weight[i][j] < INT_MAX &&\
                distance[i] + $weight[i][j] < distance[j]) 
            distance[j] = distance[i] + $weight[i][j]
            prev[j] = i
        end
        if (distance[j] < min) 
            min = distance[j];  nxt = j
        end
    end
end while (min < INT_MAX)
printf("点  直前の点  最短距離\n")
for i in 1..n
    if (i != START && visited[i])
        printf("%2d%10d%10d\n", i, prev[i], distance[i])
    end
end

exit 0