#include <iostream>

include <vector>
using namespace std;
struct Line
{
    int Vs;
    int Vt;
};
void main()
{
    int i,j,sourse,temp,min,min_node;
    int node = 8;
    int inf = 100;
    int Graph[8][8] =       {0,    2,   1,   8, 100, 100, 100, 100,
                             2,    0, 100,   6,   1, 100, 100, 100,
                             1,  100,   0,   7, 100, 100,   9, 100,
                             8,    6,   7,   0,   5,   1,   2, 100,
                           100,    1, 100,   5,   0,   3, 100,   9,
                           100,  100, 100,   1,   3,   0,   4,   6,
                           100,  100,   9,   2, 100,   4,   0,   3,
                           100,  100, 100, 100,   9,   6,   3,   0 };
    int w[8] = {0};
    int flag[8]  = {0};
    int influence_node[8] = {0};
    for(i = 0; i < node; i ++)
        w[i] = inf;
    vector< Line > line_set;
    cout << "please input the sourse :";
    cin >> sourse;
    Line line_1,line_2;
    line_1.Vs = sourse;
    line_1.Vt = sourse;
    line_set.push_back(line_1);
    w[sourse] = 0;
    flag[sourse] = 1;
    int num = node;

while(num - 1)
{ 

    line_1 = line_set.back();
    for(j = 0; j < node; j ++)
    {
        if(flag[j] == 0)
        {
            temp = Graph[line_1.Vt][j] + w[line_1.Vt];
            if(temp < w[j])
            {
                w[j] = temp;
                influence_node[j] = line_1.Vt;
            }
        }
    }
    min = 100;
    for(j = 0; j < node; j ++)
    {
        if(flag[j] == 0)
        {
            if(w[j] < min)
            {
                min = w[j];
                min_node = j;
            }
        }
    }
    flag[min_node] = 1;
    line_2.Vs = influence_node[min_node];
    line_2.Vt = min_node;
    line_set.push_back(line_2);
    num --;        
}
vector< Line >::iterator it;
for(it = line_set.begin(); it != line_set.end(); it ++)
{
    cout << it->Vs << " " << it->Vt << endl;
}

}</pre>