城市规划

【问题描述】

N城准备开发一片荒地，目前已经规划好了一些居民点，还要建些道路。由于经费问题，他们想在任意两点间的距离最短的前提下，用尽可能少的投资把各个点连接起来。需要注意的是并不是任意两个居民点间都能直接相连。给出两两居民点间建路的花费(与长度成正比)，你可以帮他们选择一个最佳方案吗?

【输入格式】

第1行是一个数N(N<100)，表示有N个居民点。
以下的N行每行有N个数，第i行第j个数表示居民点i到居民点J问建路的花费(O<w_ij<10000,w_ij=w_ij，非正数表示两地不可直连。输入数据保证有解。

【输出格式】

第1行输出总花费。
然后输出N行，每行N个数，第i行第j个数表示居民点i到居民点j的路，用1表示先取这条路，0则不选。

【输入输出样例】
输入(cityroad.in)
3
0 2 1
2 0 3
1 3 0
输出(cityroad.out)

3
0 1 1
1 0 0
1 0 0