#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;
    }
}