Go: package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

const (
	MAX   = 100
	INFTY = 1 << 21
	NIL   = -1
)

const (
	WHITE = iota
	GRAY
	BLACK
)

type Graph [MAX][MAX]int

func (g *Graph) prim(n int) int {
	var (
		u, minv     = 0, 0
		d, p, color [MAX]int
	)

	for i := 0; i < n; i++ {
		d[i] = INFTY
		p[i] = -1
		color[i] = WHITE
	}
	d[0] = 0

	for {
		minv = INFTY
		u = -1
		for i := 0; i < n; i++ {
			if minv > d[i] && color[i] != BLACK {
				u = i
				minv = d[i]
			}
		}

		if u == -1 {
			break
		}

		color[u] = BLACK
		for v := 0; v < n; v++ {
			if color[v] != BLACK && g[u][v] != INFTY {
				if d[v] > g[u][v] {
					d[v] = g[u][v]
					p[v] = u
					color[v] = GRAY
				}
			}
		}
	}

	sum := 0
	for i := 0; i < n; i++ {
		if p[i] != -1 {
			sum += g[i][p[i]]
		}
	}

	return sum
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	var g Graph
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			sc.Scan()
			e, _ := strconv.Atoi(sc.Text())
			if e == -1 {
				g[i][j] = INFTY
				continue
			}
			g[i][j] = e
		}
	}

	return fmt.Sprint(g.prim(n))
}

func main() {
	fmt.Println(answer(os.Stdin))
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;

#if 0
所用時間: 1h

感想: 思ったより実装すべきコード量が多かった。DisjointSetは今後も使う機会が多そうなので、クラス化してみた。
Pの配列を動的に確保するよう工夫した、良い復習になった。

#endif

int N, buff, M = 0, SUM = 0, A[101][101], cost[5000], dpt[5000], dst[5000];//A[Y][X]
vector<pair<int, int> > edges;

class disjointSet {
private:
    int* P;
    
public:
    disjointSet(){
        P = new int[100000];
    }
    disjointSet(int N){     
        P = new int[N];
    }
    ~disjointSet(){
        delete[] P;
    }

    void init(int N){ //木構造の初期化
        for(int i = 0; i <= N; ++i){
            P[i] = i;
        }
    }

    int root(int a){ //根の参照
        if(P[a] == a) return a;
        return (P[a] = root(P[a]));
    }

    bool is_same_set(int a, int b){ //同じ根か?
        return root(a) == root(b);
    }

    void unite(int a, int b){
        P[root(a)] = root(b); //aのrootをbの子にする
    }
};


void preprocess(){//辺の前処理
  for(int r = 0; r < N; ++r){
    for(int c = r+1; c < N; ++c){
      if (A[r][c] > -1) {
        cost[M] = A[r][c];
        dpt[M] = r;
        dst[M] = c;
        M++;
      }
    }
  }

  //for(int i = 0; i < M; ++i) cout << cost[i] << endl;

  for(int i = 0; i < M; ++i){
    edges.push_back(make_pair(cost[i], i));
  }
  // for(int i = 0; i < M; ++i) cout << edges[i].first << " " << edges[i].second << endl;

  sort(edges.begin(), edges.end());

  // for(int i = 0; i < M; ++i) cout << edges[i].first << " " << edges[i].second << endl;

}

void solve(){
  disjointSet Union(100000);

  int ans = 0;
  preprocess();

  Union.init(N);

  for(int i = 0; i < M; ++i){
    int index = edges[i].second;
    if(Union.is_same_set(dpt[index], dst[index])) continue;
    else {
      Union.unite(dpt[index], dst[index]);
      // cout << "unite " << dpt[index] << " and " << dst[index] << endl;
      ans += cost[index];
    }
  }
  cout << ans << endl;
}

int main(){

cin >> N;

for(int i = 0; i < N; ++i){
  for(int j = 0; j < N; ++j){
    cin >> buff;
    A[i][j] = buff;
    }
  }

  //行列の表示
  // cout << "Matrix:" << endl;
  // for(int row=0; row < N; ++row){
  //   for(int col = 0; col < N; ++col){
  //     cout << A[row][col];
  //   }
  //   cout << endl;
  // }

  solve();
}

C++: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_A

C++: #include <iostream>
#include <vector>
#include <queue>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;

int N;
int G[101][101];
bool used[101];

int prim()
{
   int sum = 0;
   priority_queue< pii, vector<pii>, greater<pii> > pq;
   pq.push( pii(0, 0) );

   while( !pq.empty() ){
      const pii tmp = pq.top(); pq.pop();
      if( tmp.fi == -1 || used[ tmp.se ]++ )continue;
      sum += tmp.fi;

      rep(i, N)
         pq.push( pii( G[tmp.se][i], i ) );
   }
   return (sum);
}

int main()
{
   ios::sync_with_stdio(false), cin.tie(0);
   cin >> N;

   rep(i, N)rep(j, N){
      cin >> G[i][j];
   }
   cout << prim() << '\n';
}