/**APM-Prim**/
#include<bits/stdc++.h>
using namespace std;

const int maxN=(2e5)+5;
int dp[maxN],pre[maxN];
class Heap
{
    private:
    int H[maxN];
    int P[maxN];
    int dim;
    public:

    inline void upHeap(int pos)
    {
        while(dp[H[pos]]<dp[H[pos/2]])
        {
            swap(P[H[pos]],P[H[pos/2]]);
            swap(H[pos],H[pos/2]);
            pos>>=1;
        }
    }

    inline void downHeap(int pos)
    {
        do
        {
            int best=pos;
            int son=2*pos;
            if(dp[H[son]]<dp[H[best]]) best=son;
            son++;
            if(dp[H[son]]<dp[H[best]]) best=son;
            if(best==pos) break;

            swap(P[H[pos]],P[H[best]]);
            swap(H[pos],H[best]);
            pos=best;
        }while(1);
    }

    inline void Hinsert(int x)
    {
        H[++dim]=x;
        P[x]=dim;
        upHeap(dim);
    }

    inline void Hdelete(int x)
    {
        swap(P[H[dim]],P[H[x]]);
        swap(H[x],H[dim]);
        dim--;
        downHeap(x);
    }
    inline int getPos(int x)
    {
        return P[x];
    }
    inline int getSize()
    {
        return dim;
    }
    inline int top()
    {
        return H[1];
    }
}q;



int n,m,x,y,z;
vector<pair<int,int> > edges,v[maxN];

const int inf=(1e9);
int sol;
bool seen[maxN],inSet[maxN];


int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);


    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);

        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }

    dp[1]=0;

    for(int i=2;i<=n;i++)
        dp[i]=inf;


    q.Hinsert(1);

    int nodes=0;
    while(q.getSize())
    {
        int nod=q.top();
        int cost=dp[nod];

        q.Hdelete(1);

        seen[nod]=1;
        sol+=cost;
        if(nod!=1)
            edges.push_back(make_pair(pre[nod],nod));

        for(auto it:v[nod])
        {
            int z=it.second;
            if(seen[it.first]) continue;
            if(dp[it.first]>z)
            {
                if(dp[it.first]!=inf)
                {
                    int P=q.getPos(it.first);
                    q.Hdelete(P);
                }
                pre[it.first]=nod;
                dp[it.first]=z;
                q.Hinsert(it.first);

            }
        }
    }

    printf("%d\n",sol);
    printf("%d\n",n-1);
    for(auto it:edges)
        printf("%d %d\n",it.first,it.second);

    return 0;
}