#include <fstream>
#define INF 100000
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

void citire();
void init();
void prim();
void afisare();

int cmin[1001], M[1001], start, n, m, marime[1001], sum;
int tata[1001];
struct
{
    int x, cost;
}G[1001][1001];

int main()
{
    citire();
    init();
    prim();
    afisare();
    return 0;
}

void citire()
{
    int i, l, c, money;
    fin >> n >> m >> start;
    for(i=1;i<=m;i++)
    {
        fin >> l >> c >> money;
        G[l][++marime[l]].x=c;
        G[c][++marime[c]].x=l;
        G[l][marime[l]].cost=money;
        G[c][marime[c]].cost=money;
    }
}

void init()
{
    int i, j;
    M[0]=1;
    M[start]=1;
    for(j=1;j<=marime[start];j++)
        cmin[G[start][j].x]=G[start][j].cost;
    for(i=1;i<=n;i++)
    {
        if(cmin[i]==0)
            cmin[i]=INF;
        tata[i]=start;
    }
    tata[start]=0;
    cmin[start]=0;
}

void prim()
{
    int i, costmin, minimvf, tatavf, j, k;
    for(i=1;i<=n-1;i++)
    {
        while(M[0]<n)
        {
            costmin=INF;
            for(j=1;j<=n;j++)
                if(M[j])
                {
                    for(k=1;k<=marime[j];k++)
                        if(G[j][k].cost<costmin&&M[G[j][k].x]==0)
                        {
                            costmin=G[j][k].cost;
                            minimvf=G[j][k].x;
                            tatavf=j;
                        }
                }
            tata[minimvf]=tatavf;
            cmin[minimvf]=costmin;
            M[minimvf]=1;
            M[0]++;
        }
    }
}

void afisare()
{
    int i;
    for(i=1;i<=n;i++)
        sum+=cmin[i];
    fout << sum << '\n' << n-1 << '\n';
    for(i=2;i<=n;i++)
        fout << i << ' ' << tata[i] << '\n';
}