#include <fstream>
using namespace std;
# define MAXIM 2000000000
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,ns,mat[5000][5000],viz[50000],t[50000],C[50000],s[1000],cost;
void APM()
{
    int i,j,k,ns,mini;
    ns=1;
    for(i=1;i<=n;i++)
        s[i]=ns;
    s[ns]=0;
    for(k=2;k<=n;k++)
    {
        mini=MAXIM;
        for(i=1;i<=n;i++)
            if(s[i])
                if(mat[s[i]][i]<mini)
                {
                    mini=mat[s[i]][i];
                    j=i;
                }
        t[j]=s[j];
        s[j]=0;
        cost=cost+mini;
        for(i=1;i<=n;i++)
            if(s[i])
                if(mat[i][j]<mat[i][s[i]])
                s[i]=j;

    }


}
int main()
{int a,b,c,x,j,i;
  in>>n>>m;
  for(i=1;i<=m;i++)
  {
      in>>a>>b>>c;
      if(mat[a][b]==0&&mat[b][a]==0)
      {mat[a][b]=c;
      mat[b][a]=c;
      }
      if(mat[a][b]!=0&&mat[b][a]!=0)
      {
          if(mat[a][b]>c&&mat[b][a]>c)
          {
              mat[a][b]=c;
              mat[b][a]=c;
          }
      }
  }
  in>>ns;
in.close();
for(i=1;i<=n;i++)
{
    for(j=1;j<=n;j++)
    {
        if(mat[i][j]==0)
            mat[i][j]=MAXIM;
    }
}
APM();
/*for(i=1;i<=n;i++)
    out<<T[i]<<" ";
out<<endl;
for(i=1;i<=n;i++)
        out<<C[i]<<" ";
*/
x=n-1;


out<<cost<<endl;
out<<x<<endl;
for(i=2;i<=n;i++)
    out<<i<<" "<<t[i]<<endl;

  out.close();

    return 0;
}