#include<cstdio>
#include<vector>
#include<algorithm>

#define N_MAX 200010
#define pb push_back
#define mp make_pair
#define INF 400000
using namespace std;

vector < pair<int,int> > G[N_MAX];
vector < pair<int,int> > Sol;

int H[N_MAX],D[N_MAX],T[N_MAX],poz[N_MAX],Nr;
long long Cost_Total=0;
bool use[N_MAX];

inline void Write_Data()
{
    vector < pair<int,int> > :: iterator it;
    pair<int,int> x;
    printf("%d\n%d\n",Cost_Total,Sol.size());
    for (it=Sol.begin();it!=Sol.end();++it)
    {
        x=*it;
        printf("%d %d\n",x.first,x.second);
    }
}

inline void swap(int a,int b)
{
    int aux;
    aux=H[a];
    H[a]=H[b];
    H[b]=aux;
    poz[H[a]]=a;
    poz[H[b]]=b;
}

inline void Heap_Down(int k)
{
    int St=k*2,Dr=k*2+1,p;
    if (St<=Nr)
        {
            p=St;
            if (D[H[Dr]]<D[H[St]] && Dr<=Nr) p=Dr;
            if (D[H[p]]<D[H[k]])
                {
                    swap(k,p);
                    Heap_Down(p);
                }
        }
}

inline void Heap_Up(int k)
{
    int t=k/2;
    if (D[H[k]]<D[H[t]] && t>0)
        {
            swap(k,t);
            Heap_Up(t);
        }
}

inline void del(int p)
{
   int aux;
   aux=H[p];
   H[p]=H[Nr];
   H[Nr]=aux;
   poz[H[Nr]]=Nr;
   poz[H[p]]=p;
   Nr--;
   if (Nr!=1) Heap_Down(p);
}

inline void APM()
{
    int nod,val;
    vector < pair<int,int> > :: iterator it;
    pair <int,int> x;
    while (Nr>0)
    {
        nod=H[1];
        del(1);
        val=D[nod];
        if (nod!=1) Sol.pb(mp(T[nod],nod));
        use[nod]=true;
        Cost_Total+=val;
        for (it=G[nod].begin();it!=G[nod].end();++it)
        {
            x=*it;
            if (!use[x.first] && D[x.first]>x.second)
                {
                    if (D[x.first]!=INF) del(poz[x.first]);
                    D[x.first]=x.second;
                    T[x.first]=nod;
                    H[++Nr]=x.first;
                    poz[x.first]=Nr;
                    Heap_Up(Nr);
                }
        }
    }
}

inline void Load_Data()
{
    int N,M,i,j,x,y,c;
    scanf("%d%d",&N,&M);
    for (i=1;i<=M;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        G[x].pb(mp(y,c));
        G[y].pb(mp(x,c));
    }
    for (i=1;i<=N;i++)
    {
        use[i]=false;
        D[i]=INF;
        poz[i]=INF;
        T[i]=0;
    }
    D[1]=0;
    H[1]=1;
    poz[1]=1;
    Nr=1;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    Load_Data();
    APM();
    Write_Data();
    fclose(stdin);
    fclose(stdout);
    return 0;
}