Planet Connection

Interview

Time limit1sMemory limit256 MB

Summary
Given a complete symmetric cost matrix, find a minimum spanning tree connecting all planets and output its total maintenance cost.
Level

Medium4 of 10

Topics
Minimum spanning tree, Graph, Greedy, Sorting
Solved
No attempts yet

Problem

The center of the Hongik Empire is planet T. Emperor Yunseok, ruler of the empire, wants to install flows between N planets in order to govern the empire effectively from planet T.

When a flow is installed between two planets, the empire's warships and trade ships can travel from one planet to the other in a negligibly short time. To maintain order, however, imperial troops must be stationed inside the flow.

If flows are installed between all planets and imperial troops are stationed inside them, the empire's finances will worsen, so Emperor Yunseok wants to connect all the planets of the empire while minimizing the flow maintenance cost.

The N planets are labeled with the integers 1,…,N, and the flow maintenance cost between planet i and planet j is Cij, which is always 0 when i = j.

As a staff member of the empire, help Emperor Yunseok connect all the planets in the empire and minimize the maintenance cost. The cost of installing the flows is ignored.

Input

The first line gives the number of planets N (1 ≤ N ≤ 1000).

The following N lines give the flow maintenance cost between each pair of planets as an N x N matrix (Cij), (1 ≤ i, j ≤ N, 1 ≤ Cij ≤ 100,000,000, Cij = Cji, Cii = 0).

Output

Print the minimum flow maintenance cost when all planets are connected.

Examples2

  1. Example 1

    Input
    3
0 2 3
2 0 1
3 1 0
    Expected output
    3

  2. Example 2

    Input
    5
0 6 8 1 3
6 0 5 7 3
8 5 0 9 4
1 7 9 0 6
3 3 4 6 0
    Expected output
    11